結果
問題 | No.86 TVザッピング(2) |
ユーザー | hotpepsi |
提出日時 | 2014-12-05 00:39:15 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 678 ms / 5,000 ms |
コード長 | 1,445 bytes |
コンパイル時間 | 541 ms |
コンパイル使用メモリ | 74,364 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-08-26 14:57:25 |
合計ジャッジ時間 | 2,750 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 116 ms
4,376 KB |
testcase_10 | AC | 678 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 1 ms
4,376 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 3 ms
4,380 KB |
testcase_15 | AC | 9 ms
4,380 KB |
testcase_16 | AC | 9 ms
4,376 KB |
testcase_17 | AC | 1 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,376 KB |
testcase_19 | AC | 1 ms
4,376 KB |
testcase_20 | AC | 1 ms
4,376 KB |
testcase_21 | AC | 188 ms
4,376 KB |
testcase_22 | AC | 1 ms
4,380 KB |
testcase_23 | AC | 4 ms
4,376 KB |
testcase_24 | AC | 1 ms
4,376 KB |
testcase_25 | AC | 1 ms
4,376 KB |
testcase_26 | AC | 1 ms
4,380 KB |
testcase_27 | AC | 1 ms
4,380 KB |
testcase_28 | AC | 1 ms
4,376 KB |
testcase_29 | AC | 101 ms
4,376 KB |
testcase_30 | AC | 2 ms
4,380 KB |
testcase_31 | AC | 1 ms
4,376 KB |
testcase_32 | AC | 1 ms
4,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) { 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; }