Codeforces Round #124 (Div. 1) B : Infinite Maze

問題概要

H*W(H,W<1500)の迷路がある。この迷路はトーラスみたいに無限に広くつながっている。スタート地点から無限に遠くに行けるかどうか判定する問題。

解法

8近傍にマップを拡大しておき、そのマップで探索する。同じ中で新しいマップにいくことができたらそのような遷移を繰り返して無限に遠くに行くことができる。1500^2*9でちょっと恐いがcharなので十分メモリは足りる。探索はDFSだとスタックオーバーフローが怖いのでBFSで書いた。
また、解が存在する場合でも鳩ノ巣原理よりキューが肥大化することはないので安心。

acceptされたコード

#include <cstdio>
#include <queue>
using namespace std;

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

int H, W;
char orig[MAX_W][MAX_W + 1];
char board[3*MAX_W][3*MAX_W + 1];
char visited[MAX_W][MAX_W];
int sy, sx;


void init(){
	scanf("%d%d ",  &H, &W);
	for(int i=0; i<H; ++i){
		scanf(" %s ", orig[i]);
	}
}

bool solve(){
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			if(orig[i][j] == 'S'){
				sy = i;
				sx = j;
				orig[i][j] = '.';
			}
		}
	}

	for(int a=0; a<3; ++a){
		for(int b=0; b<3; ++b){
			for(int i=0; i<H; ++i){
				for(int j=0; j<W; ++j){
					board[a*H+i][b*W+j] = orig[i][j];
				}
			}
		}
	}

	visited[sy][sx] = (char)(10+1+10);
	sy += H;
	sx += W;

	int HH = 3*H, WW = 3*W;

	queue< pair<int,int> > que;
	que.push(make_pair(sy, sx));
	for(;!que.empty();){
		int y = que.front().first, x = que.front().second; que.pop();
		for(int k=0; k<4; ++k){
			int ny = y + dy[k], nx = x + dx[k];
			if(ny < 0) ny += HH;
			if(ny >= HH) ny -= HH;
			if(nx < 0) nx += WW;
			if(nx >= WW) nx -= WW;
			if(board[ny][nx] != '#'){
				char p = (char)((ny / H) * 10 + (nx / W) + 10);
				if(!visited[ny%H][nx%W]){
					visited[ny%H][nx%W] = p;
					que.push(make_pair(ny, nx));
				}
				else if(visited[ny%H][nx%W] != p){
					return true;
				}
			}
		}
	}

	return false;
}

int main(){
	init();
	puts(solve() ? "Yes" : "No");

	return 0;
}