SRM 360 500pt : PrinceOfPersia

keyword

BruteForce　C++

問題概要

N*M(N,M<10)の2次元ボード上に王子と姫がいる。王子は4近傍の障害物がないマスに移動できる。王子が姫の元まで到達できないように最小何個障害物を設置すればよいか求める問題。

解法

まず、不可能な場合は王子と姫が隣接しているとき。それ以外の時、最大でも4つ置けばよいことがわかる（4近傍を全て潰す）。なので、0,1,2,3について調べればよい。3箇所の選び方はたかだか(N*M)^3程度しかなく、到達できるかの判定はO(N*M)でできるので全体の計算量O((N*M)^4)でできる。10^8で多少怪しいけど係数が小さいので間に合う（最悪ケースで500msくらい）。
ちなみに上位の一部は最大流で解いている。

#include <string.h>
#include <vector>
#include <string>
using namespace std;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

char board[10][10];
char tmp[10][10];
int N, M;

bool dfs(int y, int x){
	if(board[y][x] == 'P') return true;
	board[y][x] = '#';
	for(int k=0; k<4; k++){
		int ny = y + dy[k], nx = x + dx[k];
		if(0 <= ny && ny < N && 0 <= nx && nx < M && board[ny][nx] != '#' && dfs(ny,nx)){
			return true;
		}
	}
	return false;
}

struct PrinceOfPersia {

	int minObstacles(vector <string> maze) {
		N = maze.size(); M = maze[0].size();
		int py = -1, px = -1;
		for(int i=0; i<N; i++)for(int j=0; j<M; j++){
			tmp[i][j] = maze[i][j];
			if(tmp[i][j] == 'P'){
				py = i; px = j;
			}
		}
		for(int i=0; i<N; i++)for(int j=0; j<M; j++){
			if(j<M-1 && tmp[i][j] == 'P' && tmp[i][j+1] == 'P') return -1;
			if(i<N-1 && tmp[i][j] == 'P' && tmp[i+1][j] == 'P') return -1;
		}

		tmp[py][px] = 'Q';
		//search 0
		{
			memcpy(board, tmp, sizeof(tmp));
			if(!dfs(py,px)) return 0;
		}

		//search 1
		{
			for(int i=0; i<N; i++)for(int j=0; j<M; j++)if(tmp[i][j] == '.'){
				memcpy(board, tmp, sizeof(tmp));
				board[i][j] = '#';
				if(!dfs(py,px)) return 1;
			}
		}

		//search 2
		{
			for(int i1=0; i1<N; i1++)for(int j1=0; j1<M; j1++)if(tmp[i1][j1] == '.'){
				for(int i2=i1; i2<N; i2++)for(int j2=0; j2<M; j2++)if(tmp[i2][j2] == '.'){
					memcpy(board, tmp, sizeof(tmp));
					board[i1][j1] = board[i2][j2] = '#';
					if(!dfs(py,px)) return 2;
				}
			}
		}

		//search 3
		{
			for(int i1=0; i1<N; i1++)for(int j1=0; j1<M; j1++)if(tmp[i1][j1] == '.'){
				for(int i2=i1; i2<N; i2++)for(int j2=0; j2<M; j2++)if(tmp[i2][j2] == '.'){
					for(int i3=i2; i3<N; i3++)for(int j3=0; j3<M; j3++)if(tmp[i3][j3] == '.'){
						memcpy(board, tmp, sizeof(tmp));
						board[i1][j1] = board[i2][j2] = board[i3][j3] = '#';
						if(!dfs(py,px)) return 3;
					}
				}
			}
		}

		return 4;
	}

};