yukicoder No.424 立体迷路
問題概要
省略
解法
bfsで解いた。よくある、2次元座標上での迷路問題などで、ゴールまで行けるかの問題と同じようにやる。ただし、4方向への移動が高さの条件で制限されるので、それを確認すればよい。また、dyとdxを2倍して、2倍の距離の移動も同様に高さの条件を確認してやればいい。
具体的な実装方法は、
隣のマスへの移動で、(1)(2)(3)の条件に対しては、
|(進もうとするマスの高さ) - (現在のいるマスの高さ)| <= 1
で条件を満たせば進むことができる。
(4)は真ん中出すとき、次進もうとするところと、現在のところの座標を2で割れば、すこし楽。
ミス
1つ飛ばしの時、同じ高さじゃないといけないのね、でWAをはやした。文章を読もう。
コード
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; #define fi first #define se second #define rep(i,n) for(int i=0;i<(n);i++) int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; int h, w, sx, sy, gx, gy; string b[55]; bool used[55][55]; int main(void){ cin >> h >> w >> sy >> sx >> gy >> gx; sx--; sy--; gx--; gy--; rep(i, h) cin >> b[i]; rep(i, 55)rep(j, 55){ used[i][j] = false; } queue<pair<int, int> > q; q.push(make_pair(sy, sx)); used[sy][sx] = true; while(!q.empty()){ auto n = q.front(); q.pop(); if(n.fi == gy && n.se == gx) break; int hh = b[n.fi][n.se] - '0'; rep(i, 4){ int ny = n.fi + dy[i], nx = n.se + dx[i]; if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if(used[ny][nx]) continue; int nh = b[ny][nx] - '0'; if(abs(nh - hh) <= 1){ used[ny][nx] = true; q.push(make_pair(ny, nx)); } } rep(i, 4){ int ny = n.fi + 2 * dy[i], nx = n.se + 2 * dx[i]; if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if(used[ny][nx]) continue; int nh = b[ny][nx] - '0'; int ah = b[(ny + n.fi) / 2][(nx + n.se) / 2] - '0'; if(hh - ah > 0 && nh == hh){ used[ny][nx] = true; q.push(make_pair(ny, nx)); } } } if(used[gy][gx]) printf("YES\n"); else printf("NO\n"); return 0; }