結果
| 問題 |
No.86 TVザッピング(2)
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2017-08-04 00:07:50 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 5,000 ms |
| コード長 | 7,484 bytes |
| コンパイル時間 | 1,494 ms |
| コンパイル使用メモリ | 173,020 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-06-20 13:59:54 |
| 合計ジャッジ時間 | 2,382 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
// {{{ Templates
#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
os << "sz:" << v.size() << "\n[";
for (const auto& p : v) {
os << p << ",";
}
os << "]\n";
return os;
}
template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
os << "(" << p.first << "," << p.second
<< ")";
return os;
}
constexpr ll MOD = (ll)1e9 + 7LL;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;
// }}}
int N, M;
inline bool in(const int x, const int y)
{
return 0 <= x and x < M and 0 <= y and y < N;
}
inline int left(const int prev)
{
return (prev + 1) % 4;
}
inline int right(const int prev)
{
return (prev + 3) % 4;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
constexpr int dir[5] = {1, 0, -1, 0, 1};
cin >> N >> M;
vector<vector<bool>> ok(N, vector<bool>(M, true));
int ch = 0;
for (int i = 0; i < N; i++) {
string s;
cin >> s;
for (int j = 0; j < M; j++) {
if (s[j] == '#') {
ok[i][j] = false;
} else {
ch++;
}
}
}
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < M; j++) {
// if (ok[i][j]) {
// int neighbor = 0;
// for (int d = 0; d < 4; d++) {
// const int dx = dir[d];
// const int dy = dir[d + 1];
// const int newx = j + dx;
// const int newy = i + dy;
// if (in(newx, newy) and ok[newy][newx]) {
// neighbor++;
// }
// }
// if (neighbor != 2) {
// cout << "NO" << endl;
// return 0;
// }
// }
// }
// }
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
if (ok[y][x]) {
// left
for (int d = 0; d < 4; d++) {
const int dx = dir[d];
const int dy = dir[d + 1];
const int newx = x + dx;
const int newy = y + dy;
vector<vector<bool>> checked(N, vector<bool>(M, false));
bool used_right = false;
if (in(newx, newy) and ok[newy][newx]) {
int prevdir = d;
int posx = newx;
int posy = newy;
int cnt = 0;
while (true) {
checked[posy][posx] = true;
cnt++;
if (posx == x and posy == y) {
break;
}
int nextx = posx + dir[prevdir];
int nexty = posy + dir[prevdir + 1];
if (in(nextx, nexty) and ok[nexty][nextx] and (not checked[nexty][nextx])) {
posx = nextx;
posy = nexty;
continue;
}
nextx = posx + dir[left(prevdir)];
nexty = posy + dir[left(prevdir) + 1];
if (in(nextx, nexty) and ok[nexty][nextx] and (not checked[nexty][nextx])) {
prevdir = left(prevdir);
posx = nextx;
posy = nexty;
continue;
}
if (not used_right) {
nextx = posx + dir[right(prevdir)];
nexty = posy + dir[right(prevdir) + 1];
if (in(nextx, nexty) and ok[nexty][nextx] and (not checked[nexty][nextx])) {
prevdir = right(prevdir);
posx = nextx;
posy = nexty;
used_right = true;
continue;
}
}
break;
}
if (cnt == ch) {
cout << "YES" << endl;
return 0;
}
}
}
//right
for (int d = 0; d < 4; d++) {
const int dx = dir[d];
const int dy = dir[d + 1];
const int newx = x + dx;
const int newy = y + dy;
vector<vector<bool>> checked(N, vector<bool>(M, false));
bool used_left = false;
if (in(newx, newy) and ok[newy][newx]) {
int prevdir = d;
int posx = newx;
int posy = newy;
int cnt = 0;
while (true) {
checked[posy][posx] = true;
cnt++;
if (posx == x and posy == y) {
break;
}
int nextx = posx + dir[prevdir];
int nexty = posy + dir[prevdir + 1];
if (in(nextx, nexty) and ok[nexty][nextx] and (not checked[nexty][nextx])) {
posx = nextx;
posy = nexty;
continue;
}
nextx = posx + dir[right(prevdir)];
nexty = posy + dir[right(prevdir) + 1];
if (in(nextx, nexty) and ok[nexty][nextx] and (not checked[nexty][nextx])) {
prevdir = right(prevdir);
posx = nextx;
posy = nexty;
continue;
}
if (not used_left) {
nextx = posx + dir[left(prevdir)];
nexty = posy + dir[left(prevdir) + 1];
if (in(nextx, nexty) and ok[nexty][nextx] and (not checked[nexty][nextx])) {
prevdir = left(prevdir);
posx = nextx;
posy = nexty;
used_left = true;
continue;
}
}
break;
}
if (cnt == ch) {
cout << "YES" << endl;
return 0;
}
}
}
cout << "NO" << endl;
return 0;
}
}
}
cout << "NO" << endl;
return 0;
}