結果

問題 No.86 TVザッピング(2)
ユーザー ゴリポン先生
提出日時 2025-05-10 12:44:52
言語 D
(dmd 2.109.1)
結果
WA  
実行時間 -
コード長 1,112 bytes
コンパイル時間 2,844 ms
コンパイル使用メモリ 199,688 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 14:02:20
合計ジャッジ時間 9,949 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 3 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// Copilotより
import std;

int N, M;
string[] A;
alias P = Tuple!(int, "x", int, "y");
auto dir = [P(0, 1), P(1, 0), P(0, -1), P(-1, 0)];
int len = 0;	// '.' の個数
bool[][] visited;

// 二次元グリッドにおけるハミルトン閉路の検索(深さ優先探索)
bool hamiltonianCycle(P[] path, int x, int y)
{
	if (path.length == len)
		return abs(path[0].x - x) + abs(path[0].y - y) == 1;
	foreach (d; dir) {
		int nx = x + d.x, ny = y + d.y;
		if (nx < 0 || nx >= N || ny < 0 || ny >= M || A[nx][ny] == '#') continue;
		visited[nx][ny] = true;
		path ~= P(nx, ny);
		if (hamiltonianCycle(path, nx, ny)) return true;
		path.popBack;
		visited[nx][ny] = false;
	}
	return false;
}

void main()
{
	// 入力
	readln.chomp.formattedRead("%d %d", N, M);
	foreach (_; 0 .. N)
		A ~= readln.chomp;
	// 答えの計算と出力
	foreach (line; A)
		len += line.count('.');
	visited = new bool[][](N, M);
	foreach (i; 0 .. N) {
		foreach (j; 0 .. M) {
			if (A[i][j] == '#') continue;
			if (hamiltonianCycle([P(i, j)], i, j)) {
				writeln("YES");
				return;
			}
		}
	}
	writeln("NO");
}
0