AtCoder蟻本 初級編 2-1 全探索 ②Lake Counting

ATC001 A - 深さ優先探索

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder

概要

縦、横の迷路が与えられる。始点から終点まで到達できるかを判定せよ。

制約

方針

DFSで行けるマスの記録をつけながら、行けるマスにひたすら行く。
ヒューリスティック探索（？）のように「再帰を抜けた後に行けるマスの記録を戻す」ことはする必要がない。

解答

Submission #3854068 - AtCoder Typical Contest 001 | AtCoder

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int max_n = 505;
int h, w;
string grid[max_n];
 
int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
 
int sr, sc, gr, gc;
bool flg;
bool used[max_n][max_n];
 
void dfs(int r, int c){
	// 先に行けたことを記録する
	// dfs呼び出しの後usedを戻す、みたいなことはしなくてよい
	// （回数を記録する必要がなく、行けることだけを確認できればよい）
	used[r][c] = true;
	// cout << r << " " << c << endl;
	if(r == gr && c == gc && !flg){
		cout << "Yes" << endl;
		flg = true;
		return;
	}
 
	rep(i, 4){
		int nr = r + dr[i];
		int nc = c + dc[i];
		if(0 <= nr && nr < h
			&& 0 <= nc && nc < w
			&& grid[nr][nc] != '#' && !used[nr][nc]){
			dfs(nr, nc);
		}
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> h >> w;
	rep(i, h) cin >> grid[i];
 
	rep(i, h) rep(j, w){
		char c = grid[i][j];
		if(c == 's'){
			sr = i;
			sc = j;
		}
		if(c == 'g'){
			gr = i;
			gc = j;
		}
	}
	rep(i, h) rep(j, w) used[i][j] = false;
	flg = false;
	dfs(sr, sc);
	if(!flg) cout << "No" << endl;
}

ARC031 B - 埋め立て

概要

×のoとxからなる地図が与えられる。
xを一つだけoにすることで、全てのoを連結にできるならYesを、できないならNoを出力せよ。

制約

問題のとおり。

方針

それぞれのxのマスについて、そのマスをoにしたときに全てのoが連結になるかを確認する。

解答

Submission #3858240 - AtCoder Regular Contest 031

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int n = 10;
string base[n];
char grid[n][n];
 
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
 
void dfs(int x, int y){
	grid[x][y] = 'x';
	rep(k, 4){
		int nx = x + dx[k];
		int ny = y + dy[k];
 
		if(0 <= nx && nx < n && 0 <= ny && ny < n
		   && grid[nx][ny] == 'o') dfs(nx, ny);
 	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	rep(i, n) cin >> base[i];
 
	bool all_o = true;
	rep(i, n){
		rep(j, n){
			char c = base[i][j];
			if(c == 'x'){
				all_o = false;
				rep(k, n){
					rep(l, n){
						grid[k][l] = base[k][l];
					}
				}
				grid[i][j] = 'o';
				dfs(i, j);
 
				bool ok = true;
				rep(k, n){
					rep(l, n){
						if(grid[k][l] == 'o') {
							ok = false;
							break;
						}
					}
					if(!ok) break;
				}
				if(ok){
					cout << "YES" << endl;
					return 0;
				}
			}
		}
	}
 
	if(all_o) cout << "YES" << endl;
	else cout << "NO" << endl;
 
}