TJU-2760: Bronze Lilypad Pond

問題概要

2次元のボード上で最短路を求める問題。

解法

幅優先。

acceptされたコード

計算量O(H*W)。

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

const int MAX_W = 30;
const int INF = 1<<29;
const int dx[] = {1,1,-1,-1}, dy[] = {1,-1,1,-1};

int H, W, M1, M2;
int board[MAX_W][MAX_W];
int dist[MAX_W][MAX_W];

struct state{
	int y, x;
};

int main(){
	scanf("%d%d%d%d", &H,&W,&M1,&M2);

	int sy = -1, sx = -1, gy = -1, gx = -1;
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			scanf("%d", board[i]+j);
			if(board[i][j] == 3){
				sy = i;
				sx = j;
			}
			if(board[i][j] == 4){
				gy = i;
				gx = j;
			}
			dist[i][j] = INF;
		}
	}

	queue<state> que;
	que.push( (state){sy, sx} );
	dist[sy][sx] = 0;
	while(!que.empty()){
		state tp = que.front(); que.pop();
		int x = tp.x, y = tp.y;
		for(int i=0; i<2; i++){
			for(int k=0; k<4; k++){
				int ny = y + M1*dy[k], nx = x + M2*dx[k];
				if(0<=ny && ny<H && 0<=nx && nx<W && dist[ny][nx]==INF && board[ny][nx] != 0 && board[ny][nx] != 2){
					dist[ny][nx] = dist[y][x] + 1;
					que.push( (state){ny, nx} );
				}
			}
			swap(M1, M2);
		}
	}

	printf("%d\n", dist[gy][gx]);

	return 0;
}