結果
問題 | No.340 雪の足跡 |
ユーザー | mai |
提出日時 | 2016-06-13 19:02:31 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 337 ms / 1,000 ms |
コード長 | 2,174 bytes |
コンパイル時間 | 1,528 ms |
コンパイル使用メモリ | 173,432 KB |
実行使用メモリ | 23,284 KB |
最終ジャッジ日時 | 2023-08-01 13:32:51 |
合計ジャッジ時間 | 8,085 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
7,568 KB |
testcase_01 | AC | 2 ms
7,588 KB |
testcase_02 | AC | 2 ms
7,552 KB |
testcase_03 | AC | 2 ms
7,504 KB |
testcase_04 | AC | 3 ms
7,736 KB |
testcase_05 | AC | 2 ms
7,428 KB |
testcase_06 | AC | 2 ms
7,532 KB |
testcase_07 | AC | 3 ms
7,580 KB |
testcase_08 | AC | 2 ms
7,668 KB |
testcase_09 | AC | 2 ms
7,512 KB |
testcase_10 | AC | 2 ms
7,508 KB |
testcase_11 | AC | 4 ms
7,916 KB |
testcase_12 | AC | 4 ms
8,368 KB |
testcase_13 | AC | 4 ms
8,212 KB |
testcase_14 | AC | 23 ms
15,136 KB |
testcase_15 | AC | 25 ms
14,884 KB |
testcase_16 | AC | 16 ms
14,148 KB |
testcase_17 | AC | 30 ms
15,292 KB |
testcase_18 | AC | 28 ms
15,176 KB |
testcase_19 | AC | 30 ms
15,336 KB |
testcase_20 | AC | 150 ms
15,712 KB |
testcase_21 | AC | 91 ms
15,348 KB |
testcase_22 | AC | 9 ms
12,000 KB |
testcase_23 | AC | 213 ms
15,172 KB |
testcase_24 | AC | 130 ms
15,220 KB |
testcase_25 | AC | 146 ms
15,016 KB |
testcase_26 | AC | 25 ms
8,048 KB |
testcase_27 | AC | 7 ms
8,160 KB |
testcase_28 | AC | 29 ms
13,912 KB |
testcase_29 | AC | 221 ms
17,264 KB |
testcase_30 | AC | 169 ms
21,208 KB |
testcase_31 | AC | 304 ms
23,080 KB |
testcase_32 | AC | 336 ms
23,140 KB |
testcase_33 | AC | 294 ms
23,284 KB |
testcase_34 | AC | 337 ms
23,232 KB |
testcase_35 | AC | 281 ms
21,340 KB |
testcase_36 | AC | 281 ms
21,384 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; typedef long long int ll; int w,h; int dp[1001][1001]; int vroad[1001][1001]; int hroad[1001][1001]; int vimos[1001][1001]; int himos[1001][1001]; int main(){ int i,j,k,l; int x,y,d; int m,n; cin >>w>>h>>n; for (i=0;i<n;i++){ int u1,u2; scanf("%d",&m); scanf("%d",&u1); for (j=1;j<=m;j++){ scanf("%d",&u2); if (u1-w>=u2){ // down(flip->up) vimos[u2%w][u2/w]=max(u1/w-u2/w,vimos[u2%w][u2/w]); }else if (u1>u2){ // left himos[u2%w][u2/w]=max(u1-u2,himos[u2%w][u2/w]); }else if(u1+w>u2){ // right himos[u1%w][u1/w]=max(u2-u1,himos[u1%w][u1/w]); }else{ // up(flip->down) vimos[u1%w][u1/w]=max(u2/w-u1/w,vimos[u1%w][u1/w]); } u1=u2; } } for (x=0;x<w;x++){ i=0; for (y=0;y<h;y++){ if (i--<vimos[x][y] && vimos[x][y]) i=vimos[x][y]-1; vroad[x][y]=(0<=i); } } for (y=0;y<h;y++){ i=0; for (x=0;x<w;x++){ if (i--<himos[x][y] && himos[x][y]) i=himos[x][y]-1; hroad[x][y]=(0<=i); } } //for (y=0;y<h;y++){ // for (x=0;x<w;x++){ // printf("%d%d ",vroad[x][y],hroad[x][y]); // } // cout<<endl; //} queue<vector<int>> q; q.push(vector<int>{0,0,0}); while (!q.empty()){ vector<int> &e=q.front(); x=e[0];y=e[1];d=e[2];q.pop(); if (dp[x][y]) continue; if (x==w-1 && y==h-1){ cout<<d<<endl; return 0; } //printf("%d %d %d\n",x,y,d); dp[x][y]=1; if (x!=0 && hroad[x-1][y]){q.push(vector<int>{x-1,y,d+1});} if ( hroad[x ][y]){q.push(vector<int>{x+1,y,d+1});} if (y!=0 && vroad[x][y-1]){q.push(vector<int>{x,y-1,d+1});} if ( vroad[x][y ]){q.push(vector<int>{x,y+1,d+1});} } cout<<"Odekakedekinai.."<<endl; return 0; }