結果

問題 No.2928 Gridpath
コンテスト
ユーザー a1048576
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0