| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2886 人关注过本帖
标题:电子老鼠走迷宫(广搜)WA
只看楼主 加入收藏
康明贤
Rank: 2
来 自:NWPU
等 级:论坛游民
帖 子:46
专家分:32
注 册:2017-10-23
结帖率:75%
收藏
 问题点数:0 回复次数:3 
电子老鼠走迷宫(广搜)WA
1042.电子老鼠闯迷宫

时限:1000ms 内存限制:10000K  总时限:3000ms

描述

有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫,黑色部分表示建筑物,白色部分是路。电子老鼠可以在路上向上、下、左、右行走,每一步走一个格子。现给定一个起点S和一个终点T,求出电子老鼠最少要几步从起点走到终点。

输入

本题包含一个测例。在测例的第一行有四个由空格分隔的整数,分别表示起点的坐标S(x.y)和终点的坐标T(x,y)。从第二行开始的12行中,每行有12个字符,描述迷宫的情况,其中'X'表示建筑物,'.'表示路.

输出

输出一个整数,即电子老鼠走出迷宫至少需要的步数。

输入样例

2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX

输出样例

28

程序代码:
#include <stdio.h>
#include <string.h>

struct note
{
    int x;//横坐标
    int y;//纵坐标
    int s;//步数
};


int main()
{

   struct note que[145];

   int book[13][13] = {0};
   char a[13][13];

   int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

   int head,tail;
   int i,k,n=12,m=12,startx,starty,p,q,tx,ty,flag;

   scanf("%d %d %d %d",&startx,&starty,&p,&q);
   getchar();
    for(i=1;i<=n;i++)
     gets(a[i]);
   //队列初始化
   head = 1;
   tail = 1;

   //往队列插入迷宫入口坐标
   que[tail].x = startx;
   que[tail].y = starty;
   que[tail].s = 0;
   tail++;
   book[startx][starty] = 1;

   flag = 0;//用来标记是否到达目标点,0表示暂未,1表示到达

   //当队列不为空时循环
   while(head<tail)
   {
          //枚举四个方向
       for (k=0;k<=3;k++)
       {
           //计算下一个点的坐标
           tx = que[head].x+next[k][0];
           ty = que[head].y+next[k][1];
           //判断是否越界
           if (tx<1||tx>n||ty<1||ty>m)
           {
               continue;
           }
           if(a[tx][ty]=='.'&&book[tx][ty]==0)
           {
               book[tx][ty] = 1;
               que[tail].x = tx;
               que[tail].y = ty;
               que[tail].s = que[head].s+1;
               tail++;
           }
           if (tx==p&&ty==q)
           {
               flag = 1;
               break;
           }
       }
       if (flag == 1)
   {
       break;
   }
   head++;
   }

   printf("%d\n",que[tail-1].s);

   return 0;
}
/*
6 6 11 11
XXXXXXXXXXXX
X..........X
X.XXXXXXXX.X
X.X......X.X
X.X.XXXX.X.X
X.X.X..X.X.X
X.X.XX.X.X.X
X.X.XX.X.X.X
X.X....X.X.X
X.XXXXXX.X.X
X........X.X
XXXXXXXXXXXX
58
*/
/*
11 11 4 4
XXXXXXXXXXXX
X........XXX
X.XXXXXX...X
X...XX.XXX.X
X.XXXX.....X
X.X..X..X.XX
X.X....XX.XX
X...XX..X.XX
X..XXXX.X.XX
X.XXXX.....X
X..X...XXX.X
XXXXXXXXXXXX
20
*/[code]
[/code]
最后两个测例,WA!!!
搜索更多相关主题的帖子: 电子 迷宫 表示 int head 
2018-11-13 13:29
康明贤
Rank: 2
来 自:NWPU
等 级:论坛游民
帖 子:46
专家分:32
注 册:2017-10-23
收藏
得分:0 
#include<iostream>
#include<queue>
using namespace std;

void bfs();

int x1,y1,x2,y2;
int used[50][50]={0} ;
int s[20][20]={0};
char route[20][20]={0};

queue <int> x;
queue <int> y;                    //在这里需要考虑一个二维的情况,故需要给x,y各一个队列

int main()
{
    int i,j;
     cin>>x1>>y1>>x2>>y2;
    x.push(x1);
    y.push(y1);                    //相当于识别起始位置

    for(i=1;i<=12 ;i++)
    {
        for(j=1;j<=12;j++)
        {
            cin>>route[i][j];
        }
    }

    bfs();
     return 0;
}

void bfs()
{
    int i,j,flag=1;
    while(flag == 1)
    {
        if(s[x2][y2] != 0)                //在没走到终点之前,终点位置的数值始终为0
        //一旦发现不是0了,说明计数已经“计到了”这个位置。当前数值也就代表了步数
        //因为采取了广搜,所以不必担心,首先到达终点的情况肯定是“最小步数”的情况

        {
            cout<<s[x2][y2]<<endl;
            break;
        }

        x1=x.front();
        y1=y.front();        //(x1,y1)始终为当前所在的位置
        x.pop();
        y.pop();
        used[x1][y1]=1;        //走过的不能重复走了!!!!! 之前忘了这个,结果走了很多重复的路!!!!!!!!!!!
        if(route[x1-1][y1] == '.'&&used[x1-1][y1]==0)        //向上走得通
        {
            x.push(x1-1);
            y.push(y1);
            s[x1-1][y1]=s[x1][y1]+1;
        }

        if(route[x1+1][y1] == '.'&&used[x1+1][y1]==0)        //向下走得通
        {
            x.push(x1+1);
            y.push(y1);
            s[x1+1][y1]=s[x1][y1]+1;
        }

        if(route[x1][y1-1] == '.'&&used[x1][y1-1]==0)        //向左走得通
        {
            x.push(x1);
            y.push(y1-1);
            s[x1][y1-1]=s[x1][y1]+1;
        }

        if(route[x1][y1+1] == '.'&&used[x1][y1+1]==0)        //向右走得通
        {
            x.push(x1);
            y.push(y1+1);
            s[x1][y1+1]=s[x1][y1]+1;
        }

    }
}

千里之行,始于足下。
2018-11-23 11:31
wlxy_wang
Rank: 5Rank: 5
等 级:职业侠客
威 望:2
帖 子:77
专家分:303
注 册:2018-11-2
收藏
得分:0 
2018-11-23 12:56
喔喔我
Rank: 1
等 级:新手上路
帖 子:13
专家分:2
注 册:2018-12-8
收藏
得分:0 
2018-12-08 19:56
快速回复:电子老鼠走迷宫(广搜)WA
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016521 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved