Algoogle

Algorithm for Programming Contest

AOJ 2447 A Two Floors Dungeon

Category: AOJ Tag: bfs

A Two Floors Dungeon

問題概要


2階建ての迷路があって, 壁と階段以外の各場所は始め1階の高さにあるか2階の高さにある.
2階の高さにある場所の1階部分には入れないし, またその逆も入れない.
スイッチを押すと対応する場所の高さが反対になる.
スイッチを押したり階段を昇り降りしたり上下左右に移動するのに1ステップ使う.
このときスタート地点からゴールまでの最初のステップを求めよ.

解法


現在位置とスイッチの使用状況を状態としてbfsすればよい.
各スイッチを使ったかどうかをbitで持って, 各位置には何番のスイッチが影響するかをbitで持つと操作がしやすい.

コード


(2447.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
const int di[] = {1,0,-1,0}, dj[] = {0,1,0,-1};
struct state{ int i, j, f, used;};
int stage[2][64][64], sw[64][64];
int si, sj, ti, tj, W, H, S;
int dist[64][64][2][1024];

int solve(){
    memset(dist, -1, sizeof(dist));
    queue<state> q;
    q.push((state){si,sj,0,0});
    dist[si][sj][0][0] = 0;
    while(!q.empty()){
        state s = q.front(); q.pop();
        int dis = dist[s.i][s.j][s.f][s.used];
        if(s.i == ti and s.j == tj and
           s.f == __builtin_popcount(sw[s.i][s.j]&s.used)%2) return dis;

        if(stage[0][s.i][s.j] == 10 and dist[s.i][s.j][s.f^1][s.used] < 0){
            dist[s.i][s.j][s.f^1][s.used] = dis+1;
            q.push((state){s.i,s.j,s.f^1,s.used});
        }
        int cf = (s.f+__builtin_popcount(sw[s.i][s.j]&s.used))%2;
        if(0 <= stage[cf][s.i][s.j] and stage[cf][s.i][s.j] < 10){
            int nu = s.used ^ (1<<stage[cf][s.i][s.j]), nf = s.f;
            if(sw[s.i][s.j] & (1<<stage[cf][s.i][s.j])) nf ^= 1;
            if(dist[s.i][s.j][nf][nu] < 0){
                dist[s.i][s.j][nf][nu] = dis+1;
                q.push((state){s.i,s.j,nf,nu});
            }
        }
        rep(d,4){
            int ni = s.i+di[d], nj = s.j+dj[d];
            int f = (s.f+__builtin_popcount(sw[ni][nj]&s.used))%2;
            if(stage[f][ni][nj]>=0 and dist[ni][nj][s.f][s.used] < 0){
                dist[ni][nj][s.f][s.used] = dis+1;
                q.push((state){ni,nj,s.f,s.used});
            }
        }
    }
    return -1;
}

void input(){
    cin >> W >> H;
    string s;
    memset(stage,-1,sizeof(stage));
    rep(i,H){
        cin >> s;
        rep(j,W){
            if(s[j] == '%') si = i, sj = j, stage[0][i][j] = 11;
            else if(s[j] == '&') ti = i, tj = j, stage[0][i][j] = 11;
            else if(s[j] == '_') stage[0][i][j] = 11;
            else if(s[j] == '^') stage[1][i][j] = 11;
            else if(s[j] == '|') stage[0][i][j] = stage[1][i][j] = 10;
            else if('a' <= s[j] and s[j] <= 'j') stage[0][i][j] = s[j] - 'a';
            else if('A' <= s[j] and s[j] <= 'J') stage[1][i][j] = s[j] - 'A';
        }
    }
    cin >> S;
    rep(k,S) rep(i,H){
        cin >> s;
        rep(j,W) if(s[j] == '*') sw[i][j] |= 1<<k;
    }
}
int main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments