Hammer_cwz_77 @ 2017-08-18 19:28:08
#include<bits/stdc++.h>
using namespace std;
int read()
{
int ret=0,ok=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')ok=-1;ch=getchar();}
for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
return ret*ok;
}
int n;
char a[105][105];
int ans[105][105];
bool vis[105][105],sea[105][105];
int bx[]={-1,1,0,0};
int by[]={0,0,-1,1};
inline void dfs(int sx,int sy)
{
sea[sx][sy]=true;
if(sx>n || sy>n || sy<=0 || sx<=0)
return;
vis[sx][sy]=1;
for(int i=sx+1;i<=n;i++)
{
if(a[i][sy]=='x')
break;
if(ans[i][sy]>ans[sx][sy]+1)
{
ans[i][sy]=ans[sx][sy]+1;
dfs(i,sy);
}
vis[i][sy]=true;
}
for(int i=sx-1;i>=1;i--)
{
if(a[i][sy]=='x')
break;
if(ans[i][sy]>ans[sx][sy]+1)
{
ans[i][sy]=ans[sx][sy]+1;
dfs(i,sy);
}
vis[i][sy]=true;
}
for(int i=sy+1;i<=n;i++)
{
if(a[sx][i]=='x')
break;
if(ans[sx][i]>ans[sx][sy]+1)
{
ans[sx][i]=ans[sx][sy]+1;
dfs(sx,i);
}
vis[sx][i]=true;
}
for(int i=sy-1;i>=1;i--)
{
if(a[sx][i]=='x')
break;
if(ans[sx][i]>ans[sx][sy]+1)
{
ans[sx][i]=ans[sx][sy]+1;
dfs(sx,i);
}
vis[sx][i]=true;
}
for(int i=1;i<=4;i++)
{
int nx=sx+bx[i];
int ny=sy+by[i];
if(nx>n || ny>n || ny<=0 || nx<=0)
continue;
if(vis[nx][ny] && !sea[nx][ny])
{
sea[nx][ny]=1;
dfs(nx,ny);
}
}
}
int main()
{
int sx,sy;
int lx,ly;
memset(ans,0x7f,sizeof(ans));
n=read();
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;
ans[i][j]=-1;
}
if(a[i][j]=='B')
{
lx=i;
ly=j;
}
}
dfs(sx,sy);
if(ans[lx][ly]==0x7f)
{
cout<<-1<<endl;
return 0;
}
cout<<ans[lx][ly]<<endl;
return 0;
}
by 首相大大 @ 2017-08-18 20:44:29
by 首相大大 @ 2017-08-18 21:19:12
惊喜意外
by iodwad @ 2017-09-16 18:18:05
深搜会爆。。。
by 陈梓熠 @ 2018-03-12 17:16:58
是-1
by 陈梓熠 @ 2018-03-12 17:17:44
@Hammer_cwz_77 第6个点是-1
by Hammer_cwz_77 @ 2018-03-14 12:45:45
@陈梓熠 尽管早就解决了,还是谢谢QWQ