Submission #813016
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
int dy[]={-1,0,1,0};
int dx[]={0,-1,0,1};
int H,W;
int sy,sx,gy,gx;
char fld[55][55];
int dist[55][55];
signed main(){
cin>>H>>W;
cin>>sy>>sx;sy--;sx--;
cin>>gy>>gx;gy--;gx--;
rep(i,H)cin>>fld[i];
fill_n(*dist,55*55,1001001001);
dist[sy][sx]=0;
queue<pint>que;
que.push(pint(sy,sx));
while(que.size()){
int y,x;
tie(y,x)=que.front();
que.pop();
rep(i,4){
int ny=y+dy[i],nx=x+dx[i];
if(ny<0||ny>=H||nx<0||nx>=W||dist[ny][nx]!=1001001001||fld[ny][nx]=='#')continue;
dist[ny][nx]=dist[y][x]+1;
que.push(pint(ny,nx));
}
}
cout<<dist[gy][gx]<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 幅優先探索 |
User |
latte0119 |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
1316 Byte |
Status |
AC |
Exec Time |
37 ms |
Memory |
1144 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 |
37 ms |
1068 KB |
subtask0_sample02.txt |
AC |
31 ms |
1100 KB |
subtask0_sample03.txt |
AC |
32 ms |
1100 KB |
subtask1_01.txt |
AC |
30 ms |
1132 KB |
subtask1_02.txt |
AC |
31 ms |
1080 KB |
subtask1_03.txt |
AC |
33 ms |
1100 KB |
subtask1_04.txt |
AC |
33 ms |
1008 KB |
subtask1_05.txt |
AC |
33 ms |
1016 KB |
subtask1_06.txt |
AC |
32 ms |
1012 KB |
subtask1_07.txt |
AC |
33 ms |
1012 KB |
subtask1_08.txt |
AC |
34 ms |
1096 KB |
subtask1_09.txt |
AC |
32 ms |
1072 KB |
subtask1_10.txt |
AC |
32 ms |
1064 KB |
subtask1_11.txt |
AC |
32 ms |
1080 KB |
subtask1_12.txt |
AC |
33 ms |
1064 KB |
subtask1_13.txt |
AC |
32 ms |
1072 KB |
subtask1_14.txt |
AC |
32 ms |
1136 KB |
subtask1_15.txt |
AC |
33 ms |
1068 KB |
subtask1_16.txt |
AC |
33 ms |
1076 KB |
subtask1_17.txt |
AC |
32 ms |
1080 KB |
subtask1_18.txt |
AC |
34 ms |
1144 KB |
subtask1_19.txt |
AC |
32 ms |
1064 KB |
subtask1_20.txt |
AC |
33 ms |
1096 KB |
subtask1_21.txt |
AC |
36 ms |
1072 KB |
subtask1_22.txt |
AC |
30 ms |
1124 KB |