srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

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