StarryWander @ 2020-11-25 20:50:18
RT,求助
题目
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
};
node off[5]={{0,0},{0,1},{1,0},{-1,0},{0,-1}};
char a[101][101];
int ex,ey,mn=1e9,n;
bool f=0;
void dfs(int x,int y,int stp,int sum){
if(x==ex&&y==ey){
if(sum<=mn) mn=sum;
f=1;
return;
}
for(int i=1;i<=4;i++){
int tx=x+off[i].x;
int ty=y+off[i].y;
if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&a[tx][ty]=='.'||a[tx][ty]=='B'){
a[tx][ty]='#';
if(i!=stp&&stp!=0) sum++;
dfs(tx,ty,i,sum);
//a[tx][ty]=0;
}
}
}
int main(){
cin>>n;
int sx,sy;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]=='A'){
sx=i;
sy=j;
}
else if(a[i][j]=='B'){
ex=i;
ey=j;
}
}
}
a[sx][sy]='#';
dfs(sx,sy,0,0);
if(f) cout<<mn;
else cout<<-1;
return 0;
}
by BYWYR @ 2020-12-25 17:57:59
同问