P1649 题目传送门

#include<bits/stdc++.h>
#define N 5005
#define INF 0x3f3f3f3f
using namespace std;
bool vis[N][N];
int ans=INF,tot,n,sx,sy,ex,ey,dp[N][N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
char ch;
bool check(int x,int y){
	if(x<1||y<1||x>n||y>n) return false;
	return !vis[x][y];
}
void dfs(int x,int y,int dir){
	if(x==ex&&y==ey){
		ans=min(ans,tot);
		return;
	}
	if(tot>dp[x][y]) return;
	dp[x][y]=tot;
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(check(nx,ny)){
			if(i!=dir&&dir!=-1) tot++;
			dfs(nx,ny,i);
			if(i!=dir&&dir!=-1) tot--;
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>ch;
			if(ch=='x') vis[i][j]=true;
			else if(ch=='A') sx=i,sy=j;
			else if(ch=='B') ex=i,ey=j;
		}
	}
	memset(dp,INF,sizeof(dp));
	dfs(sx,sy,-1);
	printf("%d\n",ans);
	return 0;
}

看不出哪儿错了......