POJ 2251 找到出口 BFS

题目在 http://poj.org/problem?id=2251

其实这个题目和普通的走迷宫（二维走迷宫思路是一样的），只不过这个题目将迷宫扩展到三维.  最短路径，BFS代码如下：

Source Code

Problem: 2251		User: hopeztm
Memory: 620K		Time: 32MS
Language: C++		Result: Accepted

• Source Code

  #include <stdio.h>
  #include <memory.h>
  #define MAX_SIZE 31
  #define MAX_Q MAX_SIZE * MAX_SIZE * MAX_SIZE
  struct Grid
  {
  int l;
  int r;
  int c;
  int nTime;
  
  const Grid operator + (const Grid &g) const
  {
  Grid newGrid = {l + g.l, r + g.r, c + g.c};
  
  return newGrid;
  }
  bool operator == (const Grid &g)const 
  {
  return l == g.l && r == g.r && c == g.c;
  }
  
  };
  
  bool maze[MAX_SIZE][MAX_SIZE][MAX_SIZE];
  Grid queue[MAX_Q];
  
  Grid sizeDirection[6] = {
  {0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}
  
  };
  
  int nLevel, nRow, nCol;
  
  bool LegalGrid(const Grid& g)
  {
  if(g.l < 0 || g.l >= nLevel || g.r < 0 || g.r >= nRow || g.c < 0 || g.c >= nCol || maze[g.l][g.r][g.c] == 1)
  {
  return false;
  }
  return true;
  }
  int BFSGetSteps(Grid &start, const Grid &exit)
  {
  int rear, front;
  
  
  
  rear = front = 0;
  
  start.nTime = 0;
  
  queue[rear++] = start;
  
  Grid current, next;
  while(rear > front)
  {
  current = queue[front++];
  
  if(current == exit)
  {
  return current.nTime;
  }
  for( int i = 0;i < 6; i++)
  {
  next = current + sizeDirection[i];
  
  if(LegalGrid(next))
  {
  maze[next.l][next.r][next.c] = 1;
  next.nTime = current.nTime + 1;
  queue[rear++] = next;
  }
  }
  
  
  
  }
  return -1;
  }
  
  int main()
  {
  while(scanf("%d%d%d", &nLevel, &nRow, &nCol))
  {
  if( nLevel == 0 && nRow == 0 && nCol == 0)
  {
  break;
  }
  
  int iLevel, iRow, iCol;
  memset(maze, 0, sizeof(maze));
  char c;
  Grid start, exit;
  char inputLine[256];
  for( iLevel = 0; iLevel < nLevel; iLevel++)
  {
  
  for( iRow = 0; iRow < nRow; iRow++)
  {
  
  scanf("%s", inputLine);
  
  for(iCol = 0; iCol < nCol; iCol++)
  {
  sscanf(inputLine + iCol, "%c", &c);
  
  if( c == '#')
  {
  maze[iLevel][iRow][iCol] = 1;
  }
  if( c == 'S')
  {
  start.l = iLevel;
  start.r = iRow;
  start.c = iCol;
  maze[iLevel][iRow][iCol] = 1;
  }
  if( c == 'E')
  {
  exit.l = iLevel;
  exit.r = iRow;
  exit.c = iCol;
  
  }
  }
  }
  }
  int steps = BFSGetSteps(start, exit);
  if(steps == -1)
  {
  printf("Trapped!\n");
  }
  else
  {
  printf("Escaped in %d minute(s).\n", steps);
  }
  }
  return 0;
  }