90分,求助,第6个点错了

P1649 [USACO07OCT] Obstacle Course S

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


|