#4762 (C++11) No.86 TVザッピング(2)

• 問題: No.86 TVザッピング(2)
• ユーザー: hotpepsi
• 提出日時: 2014-12-05 00:35:19
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,527 bytes
• コンパイル時間: 736 ms
• コンパイル使用メモリ: 73,412 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-11 15:36:48
• 合計ジャッジ時間: 2,579 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	107 ms; 5,376 KB
testcase_10	AC	615 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	WA	-
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	3 ms; 5,376 KB
testcase_15	AC	9 ms; 5,376 KB
testcase_16	AC	9 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	174 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB
testcase_23	AC	4 ms; 5,376 KB
testcase_24	AC	1 ms; 5,376 KB
testcase_25	AC	1 ms; 5,376 KB
testcase_26	WA	-
testcase_27	AC	1 ms; 5,376 KB
testcase_28	AC	1 ms; 5,376 KB
testcase_29	AC	94 ms; 5,376 KB
testcase_30	AC	1 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	1 ms; 5,376 KB

ソースコード

#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>
#include <set>
#include <map>

using namespace std;

typedef vector<string> StrVec;

int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

bool check(int N, int M, StrVec v, int total, int sx, int sy, int dir)
{
	if (total == 2) {
		return v[sy][sx + 1] == '.' || v[sy + 1][sx] == '.';
	}

	int x = sx, y = sy;
	while (true) {
		int i;
		for (i = 0; i < 2; ++i) {
			int nd = (dir + i) % 4;
			int nx = x + dx[nd], ny = y + dy[nd];
			if (v[ny][nx] == '.') {
				dir = nd, --total;
				x = nx, y = ny;
				v[y][x] = '#';
				break;
			}
		}
		if (i >= 2) {
			break;
		}
	}
	return x == sx && y == sy && total == 0;
}

bool solve(int N, int M, const StrVec &v)
{
	int total = 0;
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			if (v[i][j] == '.') {
				++total;
			}
		}
	}

	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			if (v[i][j] == '.') {
				for (int d = 0; d < 4; ++d) {
					if (check(N, M, v, total, j, i, d)) {
						return true;
					}
				}
			}
		}
	}
	return false;
}

int main(int argc, char *argv[])
{
	int N, M;
	string s;
	{
		getline(cin, s);
		stringstream ss(s);
		ss >> N >> M;
	}
	StrVec v(N+2);
	v[0] = string(102, '#');
	for (int i = 0; i < N; ++i) {
		getline(cin, s);
		v[i + 1] = "#" + s + "#";
	}
	v[N+1] = string(102, '#');

	cout << (solve(N, M, v) ? "YES" : "NO") << endl;
	return 0;
}