【题目描述】

N ∗ N ( 1 <

N <

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

【输入格式】

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

【输出格式】

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

样例输入

3 . x A . . . B x . 样例输出

2 【数据范围】

对于 100 % 100% 数据： 2 ≤ N ≤ 100 2≤N≤100

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

代码：

#include<bits/stdc++.h>
using namespace std;
int dist[101][101];
char mapp[101][101];
int n,ax,ay,bx,by,sum;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
bool ext(int ax,int ay){
	return ax>=1&&ax<=n&&ay>=1&&ay<=n&&mapp[ax][ay]!='x';
}
void dfs(int ax,int ay,int fx){
	bool flag=0;
	if(ax==bx&&ay==by)cout<<sum;
	else{
		for(int i=1;i<=4;i++){
			if(ext(ax+dx[i],ay+dy[i])){
				ax+=dx[i];
				ay+=dy[i];
				flag=1;
				if(i%2!=fx%2)sum++;
				else{
					mapp[ax+dx[i]][ay+dy[i]]='x';
				}
				dfs(ax,ay,i);
			}
			if(i==4&&flag==0){
				mapp[ax][ay]='x';
				dfs(ax-dx[fx],ay-dy[fx],1);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>mapp[i][j];
			if(mapp[i][j]=='A'){
				ax=i;
				ay=j;
			}
			if(mapp[i][j]=='B'){
				bx=i;
				by=j;
			}
		}
	}
	mapp[ax][ay]='x';
	dfs(ax,ay,1);
    return 0;
}