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; }