UVA 1253 - Infected Land

#include <bits/stdc++.h>
using namespace std;

int N;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    
struct Node {
  char grid[5][5];
  int vr, vc;
  int virus = 0;
  Node(){}
  void input(){
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        cin >> grid[i][j];
        if(grid[i][j] == '@') vr = i, vc = j;
        if(grid[i][j] == '#') virus++;
      }
    }
  }

  void print(){
    cout << " -- " << endl;
    cout << virus << endl;
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        cout << grid[i][j];
      }
      cout << endl;
    }
    cout << " -- " << endl;
    getchar();
  }

  bool operator < (const Node &other) const {
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        if(grid[i][j] < other.grid[i][j]) return true;
      }
    }
    return false;
  }

  long long hash(){
    long long res = 0;
    for(int i=0; i<N; i++){
      for(int j=0; j<N; j++){
        int val;
        if(grid[i][j] == '#') val = 0;
        else if(grid[i][j] == '.') val = 1;
        else val = 2;
        res = (res * 3) + val;
      }
    }
    return res;
  }
};

bool inside(int r, int c){
  return 0 <= r && r < N && 0 <= c && c < N;
}

Node eradicate(Node &curr){
  Node res = curr;
  int virus = 0;
  // cout << "before " << endl;
  // curr.print();
  for(int r=0; r<N; r++){
    for(int c=0; c<N; c++){
      if(curr.grid[r][c] == '@') {
        res.grid[r][c] = '@';
        res.vr = r;
        res.vc = c;
      }
      else {
        int infected = 0;
        for(int d=0; d<8; d++){
          int nr = r+dx[d];
          int nc = c+dy[d];
          if(!inside(nr, nc)) continue;
          infected += (curr.grid[nr][nc] != '.');
        }

        if(curr.grid[r][c] == '#') {
          res.grid[r][c] = (infected == 2 || infected == 3 ? '#' : '.');
        }
        else {
          res.grid[r][c] = (infected == 3 ? '#' : '.');
        }

        virus += (res.grid[r][c] == '#');
      }
    }
  }
  res.virus = virus;
  // cout << "after " << endl;
  // res.print();
  return res;
}

int bfs(Node &start){
  queue<Node> q;
  map<long long, int> dis;
  q.push(start);
  dis[start.hash()] = 0;

  while(!q.empty()){
    Node now = q.front(); q.pop();
    int vr = now.vr, vc = now.vc;
    
    if(now.virus == 0){
      return dis[now.hash()];
    }

    for(int d=0; d<8; d++){
      Node next = now;
      int nxvr = vr + dx[d], nxvc = vc + dy[d];
      if(!inside(nxvr, nxvc) || next.grid[nxvr][nxvc] == '#') continue;
      swap(next.grid[nxvr][nxvc], next.grid[vr][vc]);
      next = eradicate(next);

      if(!dis.count(next.hash())){
        dis[next.hash()] = dis[now.hash()] + 1;
        q.push(next);
      }
    }
  }

  return -1;
}

int main() {
  ios_base :: sync_with_stdio(false);
  while(cin >> N){
    if(N == 0) break;
    Node start;
    start.input();
    int ans = bfs(start);
    cout << ans << endl;
  }
}