ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1304 Infected Land

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1304

NxNのマス目でライフゲームのシミュレーションをする問題です。(0 <= N <= 5)

ライフゲームについてはこちらを参考にしてください。
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0


・解法
私は幅優先探索(bfs)で解きました。(が、他にも解き方があると思います)

キューにはstring型でマス目の状態を表現したものを入れ、キューから出すときにstring ⇒ string[n][n] と変換してウイルスの増減、バイクの動きをチェックしました。


ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cstring>
#include<cassert>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i, 0, n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1<<29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
static const int dx[]={-1,-1,-1,0,0,1,1,1};
static const int dy[]={-1,0,1,-1,1,-1,0,1};
 
int n;
string start;
map<string,int> minCost;
 
int bfs(){
  minCost.clear();
  queue<string> q;
  q.push(start);
  minCost[start] = 0;
   
  while(!q.empty()){
    string area = q.front();
    q.pop();
    string tmp[n][n],G[n][n];
    int virus = 0;
    int x,y;
     
    rep(i,area.size()){
      tmp[i/n][i%n] = area[i];
      if(area[i]=='#') virus++;
      if(area[i]=='@'){x = i/n; y = i%n;}
    }
         
    if(virus==0) return minCost[area];
           
    rep(k,8){
      int nx = x + dx[k];
      int ny = y + dy[k];
      if(0<=nx&&nx<n && 0<=ny&&ny<n && tmp[nx][ny]=="."){
        tmp[nx][ny] = "@";
        tmp[x][y] = ".";
         
        rep(i,n){
          rep(j,n){
            int count = 0;
            if(tmp[i][j]=="#"){
              rep(l,8){
                int nnx = i + dx[l];
                int nny = j + dy[l];
                if(0<=nnx&&nnx<n && 0<=nny&&nny<n && (tmp[nnx][nny]=="#" || tmp[nnx][nny]=="@")) count++;
              }
              if(count==2 || count==3) G[i][j] = "#";
              else G[i][j] = ".";
            }
            else if(tmp[i][j]=="."){
              rep(l,8){
                int nnx = i + dx[l];
                int nny = j + dy[l];
                if(0<=nnx&&nnx<n && 0<=nny&&nny<n && (tmp[nnx][nny]=="#" || tmp[nnx][nny]=="@")) count++;
              }
              if(count==3) G[i][j] = "#";
              else G[i][j] = ".";
            }
            else G[i][j] = "@";
          }
        }
         
        string in = "";
        virus = 0;
        rep(i,n){
          rep(j,n){
            if(G[i][j]=="#") virus++;
            in += G[i][j];
          }
        }
         
        if(virus==0) return minCost[area] + 1;
         
        if(minCost.find(in)==minCost.end() || minCost[in] > minCost[area] + 1){
          minCost[in] = minCost[area] + 1;
          q.push(in);
        }
      
        tmp[nx][ny] = ".";
        tmp[x][y] = "@";
      }
    }
  }
  return -1;
}
 
int main(){
  while(cin >> n, n){
    start = "";
    rep(i,n){
      string tmp;
      cin >> tmp;
      start += tmp;
    }
    cout << bfs() << endl;
  }
  return 0;
}