题目描述

Consider an N x N (1 <= N <= 100) square field composed of 1

by 1 tiles. Some of these tiles are impassible by cows and are marked with an 'x' in this 5 by 5 field that is challenging to navigate:

. . B x . . x x A . . . . x . . x . . . . . x . .

Bessie finds herself in one such field at location A and wants to move to location B in order to lick the salt block there. Slow, lumbering creatures like cows do not like to turn and, of course, may only move parallel to the edges of the square field. For a given field, determine the minimum number of ninety degree turns in any path from A to B. The path may begin and end with Bessie facing in any direction. Bessie knows she can get to the salt lick.

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

输入输出格式

输入格式

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

输出格式

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

数据规模

2<=N<=100

输入输出样例

输入样例1

3.xA...Bx.

输出样例1

2

解题思路

　　咳咳，这道题打着BFS的幌子，说实话，有点像DFS，但又不完全是。（废话）我们从一个点开始，向上下左右不停地一直搜（DFS），遇到障碍或越界停止，然后打标记，加入队列，继续搜。

题解

　　

1 #include
     
       2 using namespace std; 3 int n,x_1,x_2,y_1,y_2;  4 int mp[110][110]; 5 bool flag[110][110]; 6 int dir[4][2]={-1,0,0,-1,1,0,0,1};//四个方向  7 struct node{ 8     int x; 9     int y;10     int t;11     node(){}12     node(int xx,int yy,int tt)//坐标和转弯次数 13     {14         x=xx;15         y=yy;16         t=tt;17     }18 };19 bool in_(int x,int y)//越界判断 20 {21     return x>=1&&y>=1&&x<=n&&y<=n; 22 }23 queue
      
        q;24 int bfs(int x,int y)25 {26     q.push(node(x,y,-1));27     flag[x][y]=true;28     while(!q.empty())29     {30         node head=q.front();31         q.pop();32         for(int i=0;i<4;i++)//四个方向 33         {34             for(int j=1;;j++)//一直搜下去 35             {36                 int tx=head.x+dir[i][0]*j;37                 int ty=head.y+dir[i][1]*j;38                 if(!in_(tx,ty)||!mp[tx][ty])break;//越界或者不能走就停止 39                 if(flag[tx][ty])continue;//走过就继续向前 40                 flag[tx][ty]=true;//标记走过 41                 if(tx==x_2&&ty==y_2)return head.t+1;//到达了就输出最少转弯数 42                 q.push(node(tx,ty,head.t+1));//进入队列 43             }44         }45     }46     return -1;//没找到 47 }48 int main()49 {50     cin>>n;51     for(int i=1;i<=n;i++)52     {53         for(int j=1;j<=n;j++)54         {55             char c;56             cin>>c;57             if(c=='A')//起点 58             {59                 x_1=i;60                 y_1=j;61             }62             if(c=='B')//终点 63             {64                 x_2=i;65                 y_2=j;66             }67             if(c!='x')mp[i][j]=true;//可以走 68         }69     }70     cout<