Problem 1304 : Infected Land

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

• 問題概要

グリッドに菌がいる。
その菌は２匹か３匹周りに菌がいると生き続ける。
菌がいない地域はちょうどまわりに３匹菌がいると感染する。
それ以外では菌がいなくなる。
という条件で増えたり減ったりする。
目的は乗り物にのって菌の増加を阻害し菌を撲滅させること。
乗り物は菌がいないところに行ける。
乗り物があるところは菌に感染する条件を満たしても菌に感染しない。
乗り物のまわりのマスはその乗り物を菌とみなす。
乗り物は動かなければならない。菌がいるところには動けないので、菌に囲まれると失敗。
撲滅させることのできる最短コストをいえ。できないなら−１をだせ。
ここでいう、乗り物の移動と接するというのは、４方向ではなく８方向である。

• 解法

BFS。
コーディングしているとき、眠すぎてコードがえらいことになった。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

#define N 5

using namespace std;
int n;
const int tx[] = {0,   1, 1, 1, 0, -1, -1, -1};
const int ty[] = {-1, -1, 0, 1, 1,  1,  0, -1};

class State{
public:
  bool t[N][N];
  int x, y, cost;
  State(){
    cost = 0;
  }
  int fcnt(int x1, int y1){
    int cnt = 0;
    rep(i, 8){	
      int nx = x1 + tx[i], ny = y1 + ty[i];
      if(nx < 0 || nx >= n || ny < 0 || ny >= n)continue;
      if(t[ny][nx] || (ny == y && nx == x))cnt++;
    }
    return cnt;
  } 
  void change(){
    bool nt[N][N];
    rep(i, n){
      rep(j, n){
	nt[i][j] = t[i][j];
	if(y == i && x == j)continue;
	int cnt = fcnt(j, i);
	if(t[i][j]){
	  if(cnt == 2 || cnt == 3)continue;
	  nt[i][j] = false;
	}
	else {
	  if(cnt == 3)nt[i][j] = true;
	}
      }
    }
    rep(i, n){
      rep(j, n){
	t[i][j] = nt[i][j];
      }
    }
  }
  
  bool end(){
    bool flag = false;
    rep(i, n){
      rep(j, n){
	if(t[i][j]){
	  flag = true;
	}
      }
    }
    return !flag;
  }
  
  bool move(int d){ 
    int nx = x + tx[d], ny = y + ty[d];
    if(nx < 0 || nx >= n || ny < 0 || ny >= n)return false;
    if(t[ny][nx])return false;
    x = nx; y = ny;
    cost++;
    change();
    return true;
  }
  bool operator < (const State &s)const{
    if( x != s.x)return x < s.x;
    if( y != s.y)return y < s.y;
    rep(i, n){
      rep(j, n){
	if( t[i][j] != s.t[i][j]){
	  return t[i][j] < s.t[i][j];
	}
      }
    }
    return false;
  }
};

main(){
  while(cin >> n){
    if(n == 0)break;
    State s;
    rep(i, n){
      rep(j, n){
	char c;
	cin >> c;
	if( c == '@'){
	  s.y = i;
	  s.x = j;
	  s.t[i][j] = false;
	}
	else if( c == '#'){
	  s.t[i][j] = true;
	}
	else s.t[i][j] = false;
      }
    }
    queue<State> Q;
    set<State> S;
    Q.push(s);

    bool find = false;
    while(!Q.empty()){
      s = Q.front();   Q.pop();	
      
      if (S.find(s) != S.end())continue;
      S.insert(s);
      if(s.end()){
	find = true;
	cout << s.cost << endl;
	break;
      }
   
      bool flag = false;
      rep(i, 8){
	State now = s;	
	now.move(i);
	Q.push(now);
      }
      if(flag)break;
    }
    if(!find)cout << -1 << endl;
  }
}

がんばった。