結果
問題 | No.86 TVザッピング(2) |
ユーザー |
![]() |
提出日時 | 2015-08-26 08:38:24 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 3,749 bytes |
コンパイル時間 | 1,823 ms |
コンパイル使用メモリ | 162,412 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 12:50:37 |
合計ジャッジ時間 | 2,717 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>typedef long long ll;typedef unsigned long long ull;#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)#define REP(i,n) FOR(i,0,n)#define RANGE(vec) (vec).begin(),(vec).end()using namespace std;class TvZapping2 {public:void solve(void) {int N,M;cin>>N>>M;int cnt = 0;vector<string> A(N);REP(i,N){cin>>A[i];// 通過可能なボタンの総数を数えておくREP(j,M) if (A[i][j] == '.')++cnt;}//// 左に曲がる回数は以下のようなケースで最大 6 回まで//// ++++++++ +++// + + + +// + S++ +// + +// ++++++++++++//// 閉路に含まれるマス数は 4*(N+M) 以下なのでそれ以上なら return// よって閉路探索時間と '.' 総数は K = 4*(N+M) 以下となる。if (cnt > 4*(N+M)){cout<<"NO"<<endl;return;}// sample 3 より最大一回は右に曲がってよいとしたとき、サイクルができればよさそう。// 以下の条件があるので計算量を落とせる// * 右に曲がれるのはスタート地点のみ。スタート地点毎に計算をすれば左 or 真っ直ぐにしか進めないとみなせる// * 左に曲がるとその先はもう進めなくなるので、それ以上すすめなくなるまで真っ直ぐ進む。// O(K^2) (K=4*(N+M)) = O(N*M)// 右回りconst int dx[] = {-1,0,1,0};const int dy[] = {0,1,0,-1};// O(N*M)int sx, sy;function<bool(int,int,int,int)> search = [&](int x, int y, int d, int c) {for (int dd = 0; dd >= -1; --dd){int nd = (4+d+dd)%4;int nx = x+dx[nd];int ny = y+dy[nd];if (nx < 0 || M <= nx || ny < 0 || N <= ny)continue;if (nx==sx && ny==sy){if (cnt == c)return true;return false;}// 進めないなら左へif (A[ny][nx] != '.')continue;A[ny][nx] = '@'; // 通過フラグを立てておくbool found = search(nx,ny,nd,c+1);A[ny][nx] = '.';if (found)return true;// まっすぐか左かしか移動しないので break するbreak;}return false;};// O(N^2*M^2)REP(d, 4){REP(y,N)REP(x,M){if (A[y][x] != '.')continue;sx = x;sy = y;A[sy][sx] = '@';if (search(sx,sy,d,1)){cout<<"YES"<<endl;return;}A[sy][sx] = '.';}}cout<<"NO"<<endl;}};#if 1int main(int argc, char *argv[]){ios::sync_with_stdio(false);auto obj = new TvZapping2();obj->solve();delete obj;return 0;}#endif