NPSC2008國中組決賽 C.喵喵捉老鼠 (Queue 的應用)

g047

#include <iostream>
#include <string>
#include <map>
#include <queue>
using namespace std;
int grid[100][100],N,M;
map<char,int> tr;
enum {WALL=-3,MOUSE,SPACE,CAT};
struct Position {int r; int c;};
Position k; 

queue<Position> q;
Position moves[4]={{0,1},{1,0},{0,-1},{-1,0}};
bool FOUND;
int steps;
int main(){
 tr['#']=WALL, tr['@']=MOUSE, tr['.']=SPACE, tr['K']=CAT;
 while(cin>>N && N>0){
  for (int i=0;i<N;i++){
   string row; cin >> row;
   M = row.length();
   for (int j=0;j<M;j++){
    grid[i][j]=tr[row[j]];
    if (row[j]=='K') {k.r=i; k.c=j;};
   }
  }
  FOUND = false;
  while(!q.empty()) q.pop();
  q.push(k);
  while(!q.empty()&&(!FOUND)){
   k=q.front();q.pop();
   steps = grid[k.r][k.c]+1;
   for (int i=0;i<4 &&(!FOUND);i++){
    Position p = {k.r+moves[i].r, k.c+moves[i].c};
    switch(grid[p.r][p.c]){
    case MOUSE:
     FOUND=true;     
     break;
    case SPACE:
     grid[p.r][p.c]=steps;
     q.push(p);
    }
   }
  }
  if(FOUND)
   cout << steps << endl;
  else
   cout << "= =\"" << endl;
 }
}