結果
問題 | No.340 雪の足跡 |
ユーザー | fura |
提出日時 | 2020-01-31 18:13:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 361 ms / 1,000 ms |
コード長 | 1,260 bytes |
コンパイル時間 | 1,966 ms |
コンパイル使用メモリ | 176,964 KB |
実行使用メモリ | 69,732 KB |
最終ジャッジ日時 | 2024-09-17 06:55:10 |
合計ジャッジ時間 | 8,056 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; using graph=vector<vector<int>>; vector<int> distance(const graph& G,int s){ const int INF=INT_MAX; int n=G.size(); vector<int> d(n,INF); d[s]=0; queue<int> Q; Q.emplace(s); while(!Q.empty()){ int u=Q.front(); Q.pop(); for(int v:G[u]) if(d[v]==INF) { d[v]=d[u]+1; Q.emplace(v); } } return d; } int main(){ int h,w,n; scanf("%d%d%d",&w,&h,&n); static int rsum[1000][1000],csum[1000][1000]; rep(i,n){ int m; scanf("%d",&m); static int b[1001]; rep(j,m+1) scanf("%d",&b[j]); rep(j,m){ int y1=b[ j ]/w,x1=b[ j ]%w; int y2=b[j+1]/w,x2=b[j+1]%w; if(y1==y2){ csum[y1][min(x1,x2)]++; csum[y1][max(x1,x2)]--; } else{ rsum[min(y1,y2)][x1]++; rsum[max(y1,y2)][x1]--; } } } rep(i,h) rep(j,w-1) csum[i][j+1]+=csum[i][j]; rep(j,w) rep(i,h-1) rsum[i+1][j]+=rsum[i][j]; graph G(h*w); rep(i,h) rep(j,w) { if(rsum[i][j]>0){ G[i*w+j].emplace_back((i+1)*w+j); G[(i+1)*w+j].emplace_back(i*w+j); } if(csum[i][j]>0){ G[i*w+j].emplace_back(i*w+j+1); G[i*w+j+1].emplace_back(i*w+j); } } int ans=distance(G,0)[h*w-1]; if(ans<h*w) printf("%d\n",ans); else puts("Odekakedekinai.."); return 0; }