Submission #13446
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<bits/stdc++.h> using namespace std; typedef pair< int , int >pint; typedef vector< int >vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template < class T, class U> void chmin(T &t,U f){ if (t>f)t=f;} template < class T, class U> void chmax(T &t,U f){ if (t<f)t=f;} int dy[]={-1,0,1,0}; int dx[]={0,-1,0,1}; int H,W; char fld[111][111]; int orig,dest; vint G[11111]; int dep[11111]; int par[11111]; int topmost[11111]; void dfs( int v, int p, int d){ dep[v]=d; par[v]=p; topmost[v]=dep[v]; for (auto u:G[v]){ if (u==p) continue ; if (dep[u]==-1){ dfs(u,v,d+1); chmin(topmost[v],topmost[u]); } else { chmin(topmost[v],dep[u]); } } } signed main(){ scanf ( "%d%d" ,&H,&W); rep(i,H) scanf ( "%s" ,fld[i]); rep(i,H)rep(j,W){ if (fld[i][j]== 'S' )orig=i*W+j; if (fld[i][j]== 'G' )dest=i*W+j; if (fld[i][j]== '#' ) continue ; rep(d,4){ int ny=i+dy[d],nx=j+dx[d]; if (ny<0||ny>=H||nx<0||nx>=W||fld[ny][nx]== '#' ) continue ; G[i*W+j].pb(ny*W+nx); } } memset (dep,-1, sizeof (dep)); dfs(orig,-1,0); int v=dest; while (par[v]!=orig){ if (topmost[v]>=dep[v]-1){ cout<< "yes" <<endl; return 0; } v=par[v]; } cout<< "no" <<endl; return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0650 - メロンパン |
ユーザー名 | latte0119 |
投稿日時 | 2017-03-09 20:56:20 |
言語 | C++11 |
状態 | Accepted |
得点 | 15 |
ソースコード長 | 1682 Byte |
最大実行時間 | 25 ms |
最大メモリ使用量 | 2172 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 15 / 15 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
01_sample1.txt | AC | 21 ms | 736 KB |
1
|
01_sample2.txt | AC | 18 ms | 908 KB |
1
|
01_sample3.txt | AC | 25 ms | 964 KB |
1
|
02_random1.txt | AC | 23 ms | 1012 KB |
1
|
02_random2.txt | AC | 22 ms | 856 KB |
1
|
02_random3.txt | AC | 18 ms | 904 KB |
1
|
02_random4.txt | AC | 22 ms | 956 KB |
1
|
02_random5.txt | AC | 23 ms | 876 KB |
1
|
02_random6.txt | AC | 12 ms | 796 KB |
1
|
02_random7.txt | AC | 17 ms | 724 KB |
1
|
02_random8.txt | AC | 13 ms | 776 KB |
1
|
02_random9.txt | AC | 16 ms | 824 KB |
1
|
02_random10.txt | AC | 23 ms | 804 KB |
1
|
03_random1.txt | AC | 24 ms | 1008 KB |
1
|
03_random2.txt | AC | 14 ms | 952 KB |
1
|
03_random3.txt | AC | 18 ms | 968 KB |
1
|
03_random4.txt | AC | 22 ms | 988 KB |
1
|
03_random5.txt | AC | 21 ms | 972 KB |
1
|
03_random6.txt | AC | 25 ms | 992 KB |
1
|
04_ei1331.txt | AC | 21 ms | 876 KB |
1
|
04_ei1332.txt | AC | 15 ms | 924 KB |
1
|
04_ei1333.txt | AC | 16 ms | 972 KB |
1
|
04_ei1334.txt | AC | 21 ms | 2172 KB |
1
|
04_ei1335.txt | AC | 24 ms | 2084 KB |
1
|
05_random1.txt | AC | 20 ms | 1360 KB |
1
|
05_random2.txt | AC | 23 ms | 1136 KB |
1
|
05_random3.txt | AC | 25 ms | 1188 KB |
1
|
05_random4.txt | AC | 14 ms | 1164 KB |
1
|
05_random5.txt | AC | 25 ms | 1212 KB |
1
|
05_random6.txt | AC | 13 ms | 1332 KB |
1
|
06_handmake1.txt | AC | 23 ms | 1012 KB |
1
|