No.124 門松列(3)

No.124 門松列(3) - yukicoder

• 単純な幅優先探索。今来た4方向を保存しておいて再度訪れないようにする。
• y 方向の向きを間違えたり、門松列の条件が抜けたりしてしまった...。

class PineDecorationSequence3 {
public:
    void solve(void) {
            int W,H;
            cin>>W>>H;

            vector<vector<int>> M;
            mdv::resize(M,H,W);

            REP(y,H)
            REP(x,W)
                cin>>M[y][x];

            //   1
            // 0 * 2
            //   3
            vector<vector<vector<bool>>> vis;
            mdv::resize(vis,H,W,4,false);

            // 幅優先探索
            queue<tuple<int,int,int,int>> que;
            // (0,0) から次の移動場所を push する
            que.emplace(0,1,1,1);
            que.emplace(1,0,0,1);

            while ( !que.empty() )
            {
                int x,y,p,t;
                tie(x,y,p,t) = que.front();
                que.pop();

                if ( x == W-1 && y == H-1 )
                {
                    cout<<t<<endl;
                    return;
                }

                int dx[] = {-1,0,1,0};
                int dy[] = {0,-1,0,1};
                int px = x+dx[p];
                int py = y+dy[p];

                REP(i,4)
                {
                    int nx = x+dx[i];
                    int ny = y+dy[i];
                    int np = (i+2)%4;

                    if ( nx < 0 || W <= nx || ny < 0 || H <= ny )
                        continue;

                    // 門松列になっているか確認
                    vector<int> a3 = {M[py][px], M[y][x], M[ny][nx]};
                    sort(RANGE(a3));

                    if ( M[ny][nx] != a3[1] && M[py][px] != a3[1] )
                        continue;

                    if ( a3[0] == a3[1] || a3[1] == a3[2] || a3[2] == a3[0])
                        continue;

                    if ( vis[ny][nx][np] )
                        continue;

                    que.emplace(nx,ny,np,t+1);
                    vis[ny][nx][np] = true;
                }
            }
            cout<<-1<<endl;
    }
};