結果

問題 No.86 TVザッピング(2)
コンテスト
ユーザー koyumeishi
提出日時 2014-12-05 02:25:20
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 3,481 bytes
コンパイル時間 882 ms
コンパイル使用メモリ 87,432 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 13:57:28
合計ジャッジ時間 1,621 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

//l b r u
int x[] = {-1,0,1,0};
int y[] = {0,1,0,-1};

int dfs(vector<vector<int> > &G, vector<bool> &visit, int pos){
	visit[pos] = true;
	int ret = 1;
	for(int i=0; i<G[pos].size(); i++){
		int next = G[pos][i];
		if(visit[next]) continue;
		ret += dfs(G, visit, next);
	}
	return ret;
}

int dfs_(vector<string> &G, int n, int m, vector<bool> &visit, int pos, int start, int toward, bool right){
	visit[pos] = true;
	int ret = 1;
	//進めるだけ進む
	//すでに訪れた点にぶつかるとそこで止まる。
	int xx = pos%m + x[toward];
	int yy = pos/m + y[toward];
	while(xx>=0 && xx < m && yy>=0 && yy < n){
		if(G[yy][xx]=='.' && !visit[xx+yy*m]){
			pos = xx + yy*m;
			visit[pos] = true;
			ret++;
			
			xx = pos%m + x[toward];
			yy = pos/m + y[toward];
		}else{
			break;
		}
	}

	//次がstart地点なら終了
	if(xx>=0 && xx < m && yy>=0 && yy < n && xx+yy*m == start){
		return ret;
	}


	int next_x;
	int next_y;
	int next;

	//右に1回だけ曲がれる
	if(right==false){
		next_x = pos%m + x[(toward+3)%4];
		next_y = pos/m + y[(toward+3)%4];
		next = next_x + next_y*m;

		//曲がった先の場所に進めるなら進む
		if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && !visit[next] && G[next_y][next_x]=='.' ){
			return ret + dfs_(G,n,m,visit, next, start, (toward+3)%4, true);
		}else{
			//次でstart地点に戻っていれば終了
			if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && next == start){
				return ret;
			}
		}
	}
	
	//今いる場所から左に曲がる
	next_x = pos%m + x[(toward+1)%4];
	next_y = pos/m + y[(toward+1)%4];
	next = next_x + next_y*m;

	//曲がった先の場所に進めるなら進む
	if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && !visit[next] && G[next_y][next_x]=='.' ){
		return ret+dfs_(G,n,m,visit, next, start, (toward+1)%4, right);
	}else{
		//次でstart地点に戻っていれば終了
		if(next_x>=0 && next_x < m && next_y>=0 && next_y < n && next == start){
			return ret;
		}
	}
	
	//start地点に戻っていないのに行く先がなかったら不適切
	return -1;
	
}

int main(){
	int n,m;
	cin >> n >> m;
	vector<string> v(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}

	vector<vector<int> > G(n*m);
	vector<int> s;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(v[i][j] == '.'){
				s.push_back(i*m + j);
				for(int k=0; k<4; k++){
					int xx = j + x[k];
					int yy = i + y[k];
 					if(xx<0 || xx >= m || yy<0 || yy >= n) continue;
					if(v[yy][xx] == '.'){
						G[m*i + j].push_back(yy*m + xx);
					}
				}
			}
		}
	}

	vector<bool> visit(n*m, false);
	bool valid = dfs(G, visit, s[0]) == s.size();
	if(valid == false){
		cout << "NO" << endl;
		return 0;
	}

	valid = false;
	//最初に追加された点は必ず角になるので探索は1回で十分
	for(int i=0; i<1 && valid == false; i++){
		int start = s[i];
		int start_x = s[i]%m;
		int start_y = s[i]/m;
		for(int j=0; j<4 && valid == false; j++){
			fill(visit.begin(), visit.end(), false);
			int cnt = dfs_(v, n, m, visit, start, start, j, false);
			valid |= cnt == s.size();
		}
	}
	cout << (valid?"YES":"NO") << endl;
	return 0;
}
0