Submission #885525


Source Code Expand

#include <cstdio>
#include <queue>
#include <string>
#include <vector>
#include <utility>

using namespace std;

using pii=pair<int, int>;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;

static const int INF=1<<29;
static const int di[]={-1, 0, 1, 0};
static const int dj[]={0, -1, 0, 1};

int main() {
    int R, C, sy, sx, gy, gx;
    scanf("%d %d %d %d %d %d", &R, &C, &sy, &sx, &gy, &gx);
    --sy; --sx; --gy; --gx;

    vs c(R);
    for (int i=0; i<R; ++i) {
        char buf[55];
        scanf("%s", buf);
        c[i] = buf;
    }

    vvi dp(R, vi(C, INF)); dp[sy][sx] = 0;

    queue<pii> q; q.push(pii(sy, sx));
    while (!q.empty()) {
        int i=q.front().first, j=q.front().second; q.pop();
        if (c[i][j] != '.') continue;

        for (int k=0; k<4; ++k) {
            int I=i+di[k], J=j+dj[k];
            if (I<0 || R<=I || J<0 || C<=J) continue;
            if (dp[I][J] < dp[i][j]) continue;
            if (c[I][J] != '.') continue;

            if (I==gy && J==gx) {
                printf("%d\n", dp[i][j]+1);
                return 0;
            }

            dp[I][J] = dp[i][j] + 1;
            c[i][j] = '+';
            q.push(pii(I, J));
        }
    }

    return 0;
}

Submission Info

Submission Time
Task C - 幅優先探索
User rsk0315
Language C++11 (GCC 4.8.1)
Score 100
Code Size 1287 Byte
Status AC
Exec Time 30 ms
Memory 924 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:20:59: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d %d %d", &R, &C, &sy, &sx, &gy, &gx);
                                                           ^
./Main.cpp:26:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", buf);
                         ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 25
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 30 ms 832 KB
subtask0_sample02.txt AC 27 ms 920 KB
subtask0_sample03.txt AC 27 ms 924 KB
subtask1_01.txt AC 27 ms 912 KB
subtask1_02.txt AC 26 ms 920 KB
subtask1_03.txt AC 25 ms 924 KB
subtask1_04.txt AC 25 ms 920 KB
subtask1_05.txt AC 26 ms 916 KB
subtask1_06.txt AC 26 ms 920 KB
subtask1_07.txt AC 26 ms 916 KB
subtask1_08.txt AC 25 ms 920 KB
subtask1_09.txt AC 27 ms 920 KB
subtask1_10.txt AC 27 ms 924 KB
subtask1_11.txt AC 27 ms 920 KB
subtask1_12.txt AC 26 ms 924 KB
subtask1_13.txt AC 27 ms 920 KB
subtask1_14.txt AC 26 ms 924 KB
subtask1_15.txt AC 25 ms 924 KB
subtask1_16.txt AC 25 ms 920 KB
subtask1_17.txt AC 27 ms 920 KB
subtask1_18.txt AC 25 ms 924 KB
subtask1_19.txt AC 27 ms 916 KB
subtask1_20.txt AC 25 ms 920 KB
subtask1_21.txt AC 25 ms 916 KB
subtask1_22.txt AC 27 ms 920 KB