結果
問題 | No.340 雪の足跡 |
ユーザー | Tsuneo Yoshioka |
提出日時 | 2016-01-30 00:26:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 276 ms / 1,000 ms |
コード長 | 4,232 bytes |
コンパイル時間 | 1,043 ms |
コンパイル使用メモリ | 103,164 KB |
実行使用メモリ | 19,344 KB |
最終ジャッジ日時 | 2024-09-21 18:53:47 |
合計ジャッジ時間 | 5,208 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 32 |
ソースコード
#include <fstream> #include <iostream> #include <iostream> #include <string> #include <vector> #include <map> #include <set> #include <numeric> #include <algorithm> #include <sstream> #include <queue> #include <stdexcept> #include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <cassert> #include <unistd.h> #include <string.h> #include <stack> #include <list> using namespace std; int main(int argc, const char * argv[]) { // sleep(1000); // insert code here... ios::sync_with_stdio(false); cin.tie(0); cout.precision(15); int W, H, N; cin >> W >> H >> N; vector< vector<bool> > maw(H, vector<bool>(W, false)); vector< vector<bool> > mah(H, vector<bool>(W, false)); vector< vector< pair<int, int> > >hlines(W); vector< vector< pair<int, int> > >wlines(H); for(int n=0;n<N;n++){ int M; cin >> M; M++; int prev_h, prev_w; for(int m=0;m<M;m++){ int B; cin >> B; int w, h; w = B%W; h = B/W; // cout << "m=" << m << ",B=" << B << " w=" << w << ",h=" << h << endl; if(m>=1){ if(prev_h == h){ int w1 = prev_w, w2 = w; if(w2<w1){ swap(w1, w2); } //cout << "add wlines" << w1 << ", " << w2 << endl; wlines[h].push_back(make_pair(w1, w2)); }else if(prev_w == w){ int h1 = prev_h, h2 = h; if(h2<h1){ swap(h1, h2); } hlines[w].push_back(make_pair(h1, h2)); }else{ printf("Wrong......\n"); exit(1); } } prev_w = w; prev_h = h; } } for(int h=0;h<H;h++){ sort(wlines[h].begin(), wlines[h].end()); int endpos = -1; int cur = 0; bool prev=false; for(int w=0;w<W;w++){ //cout << "cur=" << cur << ", h=" << h << ", w=" << w << endl; while(cur < wlines[h].size() && wlines[h][cur].first==w){ //cout << "first=" << wlines[w][cur].first << ", second=" << wlines[w][cur].second << endl; endpos = max(endpos, wlines[h][cur].second); cur++; } if(w<=endpos){ if(prev){ maw[h][w-1] = true; } } prev = (w<endpos); } } for(int w=0;w<W;w++){ sort(hlines[w].begin(), hlines[w].end()); int endpos = -1; int cur = 0; bool prev = false; for(int h=0;h<H;h++){ while(cur < hlines[w].size() && hlines[w][cur].first==h){ endpos = max(endpos, hlines[w][cur].second); cur++; } if(h<=endpos){ if(prev){ mah[h-1][w] = true; } } prev = (h<endpos); } } queue< pair<int, int> > q; vector<int> used(W*H, false); q.push(make_pair(0,0)); while(!q.empty()){ auto pa = q.front(); q.pop(); int c = pa.first; int b = pa.second; if(used[b]){ continue; } used[b] = true; //cout << "c=" << c << ", b=" << b << ", w=" << b%W << ", h=" << b/W << endl; if(b==W*H-1){ cout << c << endl; exit(0); } int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; for(int d=0;d<4;d++){ int x = (b%W)+dx[d]; int y = (b/W)+dy[d]; if(x<0 || x>=W || y<0 || y>=H){ continue; } int newb = y*W+x; if( (d==0 && mah[y-1][x]) || (d==2 && mah[y][x]) || (d==1 && maw[y][x-1]) || (d==3 && maw[y][x]) ){ q.push(make_pair(c+1, newb)); } } } cout << "Odekakedekinai.." << endl; return 0; }