Submission #1497707
Source Code Expand
#include <iostream> #include <complex> #include <vector> #include <algorithm> #include <cstdio> #include <string> #include <functional> #include <cstdlib> #include <queue> #include <tuple> #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define DFOR(i,a) for(int i=(a);i>=0;i--) using namespace std; int main(){ queue<int> que; //meiro[que/R][que%R]=que, int R,C,sx,sy,gx,gy,i,j,target,tx,ty; char meiro[50][50]; int minmeiro[51][51]; cin>>R>>C>>sy>>sx>>gy>>gx; FOR(i,0,R) cin>>meiro[i]; FOR(i,1,R+1){ FOR(j,1,C+1){ if(meiro[i-1][j-1]=='#') minmeiro[i][j]=-100; else minmeiro[i][j]=-1; } } minmeiro[sy][sx]=0; que.push(sy*C+sx); while(1){ target=que.front(); if(que.empty()){ puts("error!"); exit(1); }else{ que.pop(); } ty=target/C; tx=target%C; if(tx==gx && ty==gy) break; if(minmeiro[ty][tx-1]==-1){ minmeiro[ty][tx-1]=minmeiro[ty][tx]+1; que.push(ty*C+(tx-1)); } if(minmeiro[ty][tx+1]==-1){ minmeiro[ty][tx+1]=minmeiro[ty][tx]+1; que.push(ty*C+(tx+1)); } if(minmeiro[ty+1][tx]==-1){ minmeiro[ty+1][tx]=minmeiro[ty][tx]+1; que.push((ty+1)*C+tx); } if(minmeiro[ty-1][tx]==-1){ minmeiro[ty-1][tx]=minmeiro[ty][tx]+1; que.push((ty-1)*C+tx); } } printf("%d\n",minmeiro[gy][gx]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 幅優先探索 |
User | stnae678 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1360 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 |