emmm。。。dfs的题目用bfs做。。。

回复帖子

@zlym 2018-08-10 23:16 回复

RT。。。 A了4个点,T了两个点,其他全wa。。。 代码如下:

include<bits/stdc++.h>

using namespace std;

int n,m,ans[51][51][5],a[51][51],i,j,k,x,startx,starty,endx,endy,tmpans;

char c;

void find(int x,int y,int s,int c)

{

if ((x>n)||(x<=1)||(y>m)||(y<=1)||(a[x][y]==1)) return;

if (s>=ans[x][y][c]) return;

ans[x][y][c]=s;

if (x==endx && y==endy) return; 

if (c==1) 

{

    if (a[x+1][y]!=1 && a[x+2][y]!=1) find(x+3,y,s+1,c);

    if (a[x+1][y]!=1) find(x+2,y,s+1,c);

    find(x+1,y,s+1,c);

    find(x,y,s+1,2);

    find(x,y,s+1,4);

}

if (c==2) 

{

    if (a[x][y+1]!=1 && a[x][y+2]!=1) find(x,y+3,s+1,c);

    if (a[x][y+1]!=1) find(x,y+2,s+1,c);

    find(x,y+1,s+1,c);

    find(x,y,s+1,1);

    find(x,y,s+1,3);

}

if (c==3) 

{

    if (a[x-1][y]!=1 && a[x-2][y]!=1) find(x-3,y,s+1,c);

    if (a[x-1][y]!=1) find(x-2,y,s+1,c);

    find(x-1,y,s+1,c);

    find(x,y,s+1,2);

    find(x,y,s+1,4);

}

if (c==4) 

{

    if (a[x][y-1]!=1 && a[x][y-2]!=1) find(x,y-3,s+1,c);

    if (a[x][y-1]!=1) find(x,y-2,s+1,c);

    find(x,y-1,s+1,c);

    find(x,y,s+1,3);

    find(x,y,s+1,1);

}

return;

}

int main()

{

cin>>n>>m;

for (i=1;i<=n+1;i++)

    for (j=1;j<=m+1;j++)

        for (k=1;k<=4;k++)

            ans[i][j][k]=2100000000;

for (i=1;i<=n;i++)

    for (j=1;j<=m;j++)

    {

        cin>>x;

        a[i][j]=a[i][j]||x;

        a[i+1][j]=a[i+1][j]||x;

        a[i][j+1]=a[i][j+1]||x;

        a[i+1][j+1]=a[i+1][j+1]||x;

    }

cin>>startx>>starty>>endx>>endy>>c;

if (c=='E') find(startx+1,starty+1,0,1);

if (c=='S') find(startx+1,starty+1,0,2);

if (c=='W') find(startx+1,starty+1,0,3);

if (c=='N') find(startx+1,starty+1,0,4);

/*for (k=1;k<=4;k++)
{
    for (i=1;i<=n+1;i++)
    {
        for (j=1;j<=m+1;j++)
            printf("%4d ",ans[i][j][k]);
        cout<<endl;
    }
    cout<<endl;
}*/
tmpans=min(min(min(ans[endx+1][endy+1][1],ans[endx+1][endy+1][2]),ans[endx+1][endy+1][3]),ans[endx+1][endy+1][4]);

if (tmpans==2100000000) cout<<-1;else cout<<tmpans;
return 0;

}

@zlym 2018-08-10 23:17 回复

顺带吐槽。。。自动检测有毒

@AThousandSuns 2018-08-11 00:12 回复

@zlym 请问您分不清dfs和bfs吗?这题正解bfs,您写的dfs当然会炸。

@Anguei 管理员 2018-08-11 00:32 回复

这题就是 bfs 啊

@zlym 2018-08-11 16:20 回复

不是,我现在想解决WA,tle再说