1304 Infected Land

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1304

方針

広さが5*5しかないので、BFSした。

ソース

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cassert>
using namespace std;

#define REP(i,a,b) for(i=a; i<b; ++i)
#define rep(i,n) REP(i,0,n)

int dx[8] = {0, 1, 0, -1, -1, -1, 1, 1};
int dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
int n;

struct State{
    string mp;
    int turn,x,y;
    State(string mp,int turn,int x,int y) : mp(mp), turn(turn), x(x), y(y) {;}
};

string update(string &mp) {
    int i,j,k;
    string tmp = mp;

    rep(i,n) rep(j,n) {
        int adj = 0;
        if(mp.at(i*n+j) == '@') continue;
        rep(k,8) {
            if(i+dy[k] < 0 || i+dy[k] >= n) continue;
            if(j+dx[k] < 0 || j+dx[k] >= n) continue;
            if(mp.at((i+dy[k])*n+(j+dx[k])) == '#'
               || mp.at((i+dy[k])*n+(j+dx[k])) == '@') adj++;
        }
        if(adj == 3) tmp.at(i*n+j) = '#';
        else if(adj == 2 && tmp.at(i*n+j) == '#') tmp.at(i*n+j) = '#';
        else tmp.at(i*n+j) = '.';
    }
    return tmp;
}

int bfs(string bmap,int y,int x) {
    int i,j;
    queue<State> Q;
    set<string> memo;
    memo.insert(bmap);
    Q.push(State(bmap,0,x,y));
    while(!Q.empty()) {
        State now = Q.front();
        string nmap = now.mp;
        int ii = now.turn;
        Q.pop();

        if(nmap.find("#") == string::npos) return ii;

        rep(i,8) {
            if(now.y+dy[i] < 0 || now.y+dy[i] >= n) continue;
            if(now.x+dx[i] < 0 || now.x+dx[i] >= n) continue;
            if(nmap.at((now.y+dy[i])*n+(now.x+dx[i])) == '#') continue;
            string next = string(nmap);
            next.at((now.y+dy[i])*n+now.x+dx[i]) = '@';
            next.at((now.y)*n+now.x) = '.';
            next = update(next);
            if(memo.find(next) != memo.end()) continue;
            memo.insert(next);
            Q.push(State(next,ii+1,now.x+dx[i],now.y+dy[i]));
        }
    }
    return -1;
}

int main() {
    while(cin>>n, n) {
        string imap = "",tmp;
        for(int i=0; i<n; ++i) {
            cin>>tmp;
            imap += tmp;
        }
        int pp = imap.find("@");
        cout<<bfs(imap, pp/n, pp%n)<<endl;
    }
}