Submission #11349334
Source Code Expand
#include<iostream>
#include<string>
#include<vector>
#include <queue>
#include<math.h>
#include<algorithm>
#include <numeric>
#include <utility>
#define LL long long
#define MOD 1000000007
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
LL gcd(LL C, LL D) {
if (C < D) gcd(D, C);
if (C%D == 0)return D;
else gcd(D, C%D);
}
int R, C, sy, sx, gy, gx;
char c[50][50];
int dist[50][50];
queue<pair<int,int>> Q;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int main() {
cin >> R >> C;
cin >> sy >> sx;
cin >> gy >> gx;
sy--, sx--, gy--, gx--;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> c[i][j];
dist[i][j] = -1;
}
}
Q.push(make_pair(sy, sx));
dist[sy][sx] = 0;
while (!Q.empty()) {
int y = Q.front().first;
int x = Q.front().second;
Q.pop();
rep(i, 4) {
int nx = x + dx[i], ny = y + dy[i];
if (c[ny][nx] == '.') {
if (dist[ny][nx] == -1) {
dist[ny][nx] = dist[y][x] + 1;
Q.push(make_pair(ny, nx));
}
}
}
}/*
rep(i, R){
rep(j, C) {
cout << dist[i][j];
}
cout << endl;
}*/
cout << dist[gy][gx] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 幅優先探索 |
User |
sougo002 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1228 Byte |
Status |
AC |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
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 |
1 ms |
256 KB |
subtask0_sample02.txt |
AC |
1 ms |
256 KB |
subtask0_sample03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
1 ms |
256 KB |
subtask1_06.txt |
AC |
1 ms |
256 KB |
subtask1_07.txt |
AC |
1 ms |
256 KB |
subtask1_08.txt |
AC |
1 ms |
256 KB |
subtask1_09.txt |
AC |
1 ms |
256 KB |
subtask1_10.txt |
AC |
1 ms |
256 KB |
subtask1_11.txt |
AC |
1 ms |
256 KB |
subtask1_12.txt |
AC |
1 ms |
256 KB |
subtask1_13.txt |
AC |
1 ms |
256 KB |
subtask1_14.txt |
AC |
1 ms |
256 KB |
subtask1_15.txt |
AC |
1 ms |
256 KB |
subtask1_16.txt |
AC |
1 ms |
256 KB |
subtask1_17.txt |
AC |
1 ms |
256 KB |
subtask1_18.txt |
AC |
1 ms |
256 KB |
subtask1_19.txt |
AC |
1 ms |
256 KB |
subtask1_20.txt |
AC |
1 ms |
256 KB |
subtask1_21.txt |
AC |
1 ms |
256 KB |
subtask1_22.txt |
AC |
1 ms |
256 KB |