Submission #1359042
Source Code Expand
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <map> #include <bitset> typedef long long ll; #define fi first #define se second const ll mod = 1000000007; // 123456789 using namespace std; /////////////////////////////////////////////// // // /////////////////////////////////////////////// //////////////////////////////////////////////// //////////////////////////////////////////////// int R; int C; int sy; int sx; int gy; int gx; string S[50]; int dist[50][50]; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; pair<int, int >Q[2500]; int main(){ cin>>R>>C; cin>>sy>>sx; cin>>gy>>gx; sy--; sx--; gy--; gx--; int i; int j; int x; int y; int Push = 0; int Pop = 0; for( i = 0; i < R; i++ ){ cin>>S[i]; } fill(dist[0], dist[50], -1); for( i = 0; i < R; i++ ){ for( j = 0; j < C; j++ ){ if( S[i][j] == '.' ) dist[i][j] = mod; } } dist[sy][sx] = 0; Q[Push].fi = sy; Q[Push].se = sx; Push++; while( Pop < Push ){ //ゴールについたらおしまい if( Q[Pop].fi == gy && Q[Pop].se == gx ) break; for( i = 0; i < 4; i++ ){ y = Q[Pop].fi+dy[i]; x = Q[Pop].se+dx[i]; if( dist[y][x] != -1 ){ if( dist[y][x] > dist[Q[Pop].fi][Q[Pop].se]+1 ){ dist[y][x] = dist[Q[Pop].fi][Q[Pop].se]+1; Q[Push].fi = y; Q[Push].se = x; Push++; } } } Pop++; } /* for( i = 0; i < R; i++ ){ for( j = 0; j < C; j++ ){ if( j ) printf(" "); printf("%d", dist[i][j]); } puts(""); } */ cout<<dist[gy][gx]<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 幅優先探索 |
User | Ice_in_juice |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1719 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 |