ZQU 1313拐弯

拐弯

Description

N*N ( 1 <= N <= 100 ) 方格中， 'x' 表示不能走的格子， '.'表示可以走的格子。卡门很胖，故而不好转弯。现在要从A点走到B点，请问最少要转90度弯几次？

只可以上、下、左、右四个方向行走，并且不能走出这些格子之外。开始和结束时的方向可以任意。

Input

第一行一个整数： N ，下面N行，每行N个字符，只出现字符： '.' , 'x', 'A', 'B' ，表示上面所说的矩阵格子，每个字符后有一个空格（包括每一行的最后）。

2 <= N <= 100

Output

一个整数，最少转弯次数。如果不能到达，输出-1 。

Sample Input

3

. x A

. . .

B x .

Sample Output

2

解题思路

由于BFS可以找到最短路，所以主体采用BFS。但由于同一方向上可能有多个可走格子，且拐弯个数一致。所以在这方面的处理上可利用while循环全部进队。这样可以保证在队列前面的都是拐弯数最少的。

AC代码

#include <cstdio>
const int maxn = 110;
const int inf = 1000000;
char a[maxn][maxn]; // 存放读入的地图
int flag[maxn][maxn]; // 存放走到当前点的拐弯次数
typedef struct room // 当前格子的坐标
{
 int x, y;
}room;
room st, ed; // 起点和终点
room rt[maxn*maxn]; // 行走时的队列
int front, rear; // 队列头和尾
void Init(int const & n)
{
 int i, j, k = n+1;
 for (i = 0; i < k; i++) // 未走的格子初始化为正无穷
  for (j = 0; j < k; j++)
   flag[i][j] = inf;
 for (i = 0; i < k; i++) // 加边框，限制走动范围
 {
  flag[i][0] = -1; flag[i][k] = -1;
  flag[0][i] = -1; flag[k][i] = -1;
 }
 flag[k][k] = -1;
}
void Read(int const & n) // 读入地图
{
 int i, j, k = n+1;
 for (i = 1; i < k; i++)
  for (j = 1; j < k; j++)
   scanf("%c ",&a[i][j]);
}
void FindStart(int const &n) // 查找开始和结束点
{
 int i, j, k = n+1;
 for (i = 1; i < k; i++)
  for (j = 1; j < k; j++)
  {
   if (a[i][j] == 'A')
   {
    st.x = i;
    st.y = j;
    flag[st.x][st.y] = -1; // 起点转弯个数设置为-1
   }
   else if (a[i][j] == 'B')
   {
    ed.x = i;
    ed.y = j;
   }
  }
}
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; // 四个方向
bool dfs(int const & x, int const & y) // 向四个方向深搜可走格子
{
 int v, d, i, j;
 v = flag[x][y]+1; // 转弯个数
 for (d = 0; d < 4; d++)
 {
  i = x+dir[d][0]; j = y+dir[d][1];
  // 当格子可走且转弯数大于等于当前结点走到该结点的拐弯值时，走到该结点
  while (flag[i][j]!=-1 && flag[i][j]>=v && a[i][j]!='x')
  {
   flag[i][j] = v;
   if (a[i][j] == 'B') return true; // 已经走到终点
   rt[rear].x = i; rt[rear].y = j; ++rear; // 当前可走结点进栈
   i+=dir[d][0]; j+=dir[d][1]; // 继续往该方向走
  }
 }
 return false; // 未能走到终点
}
void Play()
{
 bool yes = false;
 int x, y;
 front = rear = 0;
 rt[rear++] = st; // 起点进队
 while (front < rear)
 {
  x = rt[front].x; y = rt[front].y; // 取得队首
  if (dfs(x,y)) { yes = true; break;} // 找到时退出
  ++front; // 将第一个结点弹出
 }
 if (yes) printf("%d\n",flag[ed.x][ed.y]);
 else printf("-1\n"); // 不能走到终点时输出-1
}
int main()
{
// freopen("1313.txt","r",stdin);
 int n;
 while (~scanf("%d\n",&n))
 {
  Init(n);
  Read(n);
  FindStart(n);
  Play();
 }
 return 0;
}