結果
問題 | No.2928 Gridpath |
ユーザー |
|
提出日時 | 2024-10-12 16:15:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,521 bytes |
コンパイル時間 | 1,835 ms |
コンパイル使用メモリ | 187,180 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-12 16:15:11 |
合計ジャッジ時間 | 2,774 ms |
ジャッジサーバーID (参考情報) |
judge / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long signed main() { int h,w; cin >> h >> w; int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; x1--,y1--,x2--,y2--; vector<vector<bool>> v(h,vector<bool>(w,false)); deque<pair<pair<int,int>,vector<vector<bool>>>> q; v[x1][y1] = true; q.push_back({{x1,y1},v}); int ans = 0; while(q.size() > 0) { int x,y; tie(x,y) = q.front().first; v = q.front().second; q.pop_front(); if(x == x2 && y == y2) { ans++; continue; } for(int e = -1; e <= 1; e++) { for(int f = -1; f <= 1; f++) { if(abs(e)+abs(f) != 1) continue; if(x+e < 0 || x+e >= h || y+f < 0 || y+f >= w) continue; if(v[x+e][y+f]) continue; v[x+e][y+f] = true; bool ok = true; for(int i = 0; i < h-1; i++) for(int j = 0; j < w-1; j++) { int c = 0; for(int d = 0; d < 2; d++) for(int g = 0; g < 2; g++) c+=v[i+d][j+g]; if(c == 4) { ok = false; break; } } for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) { int c = 0; if(!v[i][j]) continue; for(int d = -1; d <= 1; d++) for(int g = -1; g <= 1; g++) { if(abs(d)+abs(g) != 1) continue; if(i+d < 0 || i+d >= h || j+g < 0 || j+g >= w) continue; if(v[i+d][j+g]) c++; } int e = 3; if(i == x1 && j == y1) e = 2; if(i == x2 && j == y2) e = 2; if(e <= c) { ok = false; break; } } if(ok) { q.push_back({{x+e,y+f},v}); } v[x+e][y+f] = false; } } } cout << ans << endl; }