問題E Robot Navigation

合同練習会

解法

BFS(幅優先探索)です。最短距離更新のときにキューに入れるのと経路数の更新をして、最短距離と等しいときは経路数の加算をしています。

コード(C++)

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

const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};
const int INF = 1e+8;

int h, w, sx, sy, gx, gy, s_dir, ans1, ans2;
string c[101];
// d[dir][y][x] := (sx, sy, s_dir) から (x, y, dir)までの最小コスト
int d[4][101][101];
// dp[dir][y][x] := (x, y, dir)までの経路数
int dp[4][101][101];

struct State{
	int x, y, dir;
	State(){}
	State(int x_, int y_, int dir_){
		x = x_; y = y_; dir = dir_;
	}
};

void solve(){
	for(int i = 0 ; i < 4 ; i++ ){
		for(int j = 0 ; j < 101 ; j++ ){
			for(int k = 0 ; k < 101 ; k++ ){
				d[i][j][k] = INF;
				dp[i][j][k] = 0;
			}
		}
	}
	
	d[s_dir][sy][sx] = 0;
	dp[s_dir][sy][sx] = 1;
	queue<State> q;
	q.push( State(sx, sy, s_dir) );
	
	ans1 = INF, ans2 = 0;
	while( !q.empty() ){
		int x = q.front().x, y = q.front().y, dir = q.front().dir; q.pop();
		
		if( x == gx && y == gy ){
			ans1 = d[dir][y][x];
			break;
		}
		
		// 右に90度回転
		int next_dir = (dir + 1) % 4;
		if( d[next_dir][y][x] == INF ){
			d[next_dir][y][x] = d[dir][y][x] + 1;
			dp[next_dir][y][x] += dp[dir][y][x] % 1000000;
			q.push( State(x, y, next_dir) );
		}else if( d[dir][y][x] + 1 == d[next_dir][y][x] ){
			dp[next_dir][y][x] += dp[dir][y][x] % 1000000;
		}
		// 右に90度回転
		next_dir = (dir + 3) % 4;
		if( d[next_dir][y][x] == INF ){
			d[next_dir][y][x] = d[dir][y][x] + 1;
			dp[next_dir][y][x] += dp[dir][y][x] % 1000000;
			q.push( State(x, y, next_dir) );
		}else if( d[dir][y][x] + 1 == d[next_dir][y][x] ){
			dp[next_dir][y][x] += dp[dir][y][x] % 1000000;
		}
		// 直進する
		int mx = x, my = y;
		for( ; true ; ){
			mx += dx[dir], my += dy[dir];
			if( mx < 0 || my < 0 || w <= mx || h <= my || c[my][mx] == '*' ) break;
			
			if( d[dir][my][mx] == INF ){
				d[dir][my][mx] = d[dir][y][x] + 1;
				dp[dir][my][mx] += dp[dir][y][x] % 1000000;
				q.push( State(mx, my, dir) );
			}else if( d[dir][y][x] + 1 == d[dir][my][mx] ){
				dp[dir][my][mx] += dp[dir][y][x] % 1000000;
			}
		}
	}
	for(int i = 0 ; i < 4 ; i++ ){
		if( d[i][gy][gx] == ans1 ){
			ans2 += dp[i][gy][gx] % 1000000;
		}
	}
	if( ans1 == INF ) ans1 = ans2 = 0;
}

int main(){
	int f[256] = {0};
	f['E'] = 1; f['S'] = 2; f['W'] = 3;
	
	while( cin >> h >> w , h || w ){
		for(int y = 0 ; y < h ; y++ ) cin >> c[y];
		
		for(int y = 0 ; y < h ; y++ ){
			for(int x = 0 ; x < w ; x++ ){
				if( c[y][x] == '.' || c[y][x] == '*' ) continue;
				
				if( c[y][x] == 'X' ){
					gx = x, gy = y, c[y][x] = '.';
				}else{
					sx = x, sy = y, s_dir = f[c[y][x]]; c[y][x] = '.';
				}
			}
		}
		solve();
		cout << ans1 << " " << ans2 << endl;
	}
}