Algoogle

Algorithm for Programming Contest

AOJ 1304 Infected Land

Category: AOJ Tag: bfs, implementation

Infected Land

問題概要


基本ルールはライフゲームと全く同じ.
ただし今回は消滅しない動ける点(車)が存在する. この点は周囲8マスの何もないところに移動できて他のマスにはウイルスと同じように見える.
このときウイルスが全滅する最小のステップ数はいくらか.

解法


各マスが感染しているかどうかと現在の車の位置の状態は高々25*2^25(<2^30)程度なので状態はすべてintのハッシュとしてもつことにする.
あとは状態遷移を題意通りしてやればよい.
各状態から遷移できる状態はかなり限られているのでこれで十分間に合う.

コード


(1304.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
#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,-1,-1,0,1,1,1,0}, dj[] = {-1,0,1,1,1,0,-1,-1};
int N, st;
map<int,int> d;

inline bool in(int i, int j){ return i >= 0 and i < N and j >=0 and j < N;}

int next_s(int s, int t){
    int ns = 0;
    rep(i,N)rep(j,N)if(i*N+j!=t){
        int cnt = 0;
        rep(dd,8){
            int ni = i+di[dd], nj = j+dj[dd];
            cnt += in(ni,nj) and ((s&(1<<(ni*N+nj))) or (ni*N+nj==t));
        }
        int c = 1<<(i*N+j), v = s&c;
        if(v and cnt > 1 and cnt < 4) ns |= c;
        else if(!v and cnt == 3) ns |= c;
    }
    return ns;
}

int solve(){
    queue<int> q;
    q.push(st);
    d[st] = 0;
    while(!q.empty()){
        int tmp = q.front(); q.pop();
        int s = tmp & ((1<<(N*N))-1), t = tmp>>(N*N);
        int td = d[tmp];
        if(s==0) return td;
        rep(dd,8){
            int ni = t/N+di[dd], nj = t%N+dj[dd];
            int nt = ni*N+nj, ntt = 1<<nt;
            if(in(ni,nj) and !(s&ntt)){
                int ns = next_s(s,nt) | (nt << (N*N));
                if(d.count(ns)) continue;
                d[ns] = td+1; q.push(ns);
            }
        }
    }
    return -1;
}

bool input(){
    cin >> N;
    st = 0; d.clear();
    rep(i,N){
        string s; cin >> s;
        rep(j,N){
            if(s[j] == '#') st |= 1<<(i*N+j);
            else if(s[j] == '@') st |= (i*N+j)<<(N*N);
        }
    }
    return N;
}

int main(){
    while(input()) cout << solve() << endl;
    return 0;
}

Comments