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; } }