即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

当然选择原谅她呀 【bfs and dfs 不同点】

编程语言 qq_37383726 6℃ 0评论

当然选择原谅她呀

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)


Total Submission(s) : 64 Accepted Submission(s) : 22


Font: Times New Roman | Verdana | Georgia


Font Size: ← →


Problem Description


小陈和小白是一对恩爱的夫妻, 可是有一天小白被困在了大魔王小张的手里, 小张将小白困在了迷宫的最右下角,于是小陈打算从迷宫的左上角出发去找到她并且原谅她呀!


Input


输入文件将包含一组或者几组数据。每组测试数据包含一个n, m(0 < n,m <= 20)表示迷宫的行数和列数。紧跟着一个n行m列的矩阵表示一个迷宫, 其中的1表示墙壁,0表示可以走的路, 只能横着走或者竖着走, 不能斜着走, 要求编程序找出从左上角到右下角最短路径的步数。


Output


左上角到右下角最短路径的步数。如果小陈没办法原谅小陈, 输出”-1”


Sample Input


5 5


0 1 0 0 0


0 1 0 1 0


0 0 0 0 0


0 1 1 1 0


0 0 0 1 0


Sample Output


8


Author


wanglang

本来就是模版水题,一直MLE 。。 问队友dalao,说试试dfs,还真ac了。Σ( ° △ °|||)︴。。 其实也是 bfs好写些,不想再构造dfs。


bfs 虽然省时间,但是却需要耗费许多的空间,dfs虽然 耗时间些,但是空间消耗的很少。。


长个记性。。


代码


BFS的代码

#include
#include
#include
using namespace std;
/************************************/
struct Node{
    int x;
    int y;
    int step;
};
int to[4][2]={1,0,-1,0,0,1,0,-1};
bool mp[23][23];
int n,m;
void getmap()
{
    int a;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a);
            mp[i][j]=!a;
        }
    }
}
queueQ;
void bfs()
{
    Node e={1,1,0};int flag=0;
    Node now,nexts;
    while(!Q.empty()) Q.pop();
    Q.push(e);
    while(!Q.empty())
    {
        now=Q.front();Q.pop();
        if(now.x==n&&now.y==m) { flag=1;break;}
        for(int i=0;i<4;i++)
        {
            nexts.x=now.x+to[i][0];
            nexts.y=now.y+to[i][1];
            nexts.step=now.step+1;
            if(mp[nexts.x][nexts.y])
            Q.push(nexts);
        }
    }
    printf("%d\n",flag?now.step:-1);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(mp,0,sizeof(mp));
        getmap();
        bfs();
    }
    return 0;
}

dfs AC代码

#include
#include
#include
using namespace std;
/************************************/
const int inf =0x3f3f3f3f;
int step;
int to[4][2]={1,0,-1,0,0,1,0,-1};
bool mp[23][23];
int n,m;
void getmap()
{
    int a;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a);
            mp[i][j]=!a;
        }
    }
}
void  dfs(int x,int y,int ge)
{
        mp[x][y]=0;
        if(x==n&&y==m) {step=min(step,ge);return;}
        int xx,yy;
        for(int i=0;i<4;i++)
        {
            xx=x+to[i][0];
            yy=y+to[i][1];
            if(mp[xx][yy])
            {
                 dfs(xx,yy,ge+1);
                 mp[xx][yy]=1;// 回溯下要
            }
        }
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(mp,0,sizeof(mp));
        getmap();
        step=inf;
        dfs(1,1,0);
        if(step==inf) printf("-1\n");
        else printf("%d\n",step);
    }
    return 0;
}

转载请注明:CodingBlog » 当然选择原谅她呀 【bfs and dfs 不同点】

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情