| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 267 人关注过本帖
标题:广度优先搜索问题,程序运行时终止,求帮忙看下哪里的错误?
只看楼主 加入收藏
青蝶
Rank: 2
等 级:论坛游民
帖 子:127
专家分:26
注 册:2018-2-4
结帖率:93.94%
  已结贴   问题点数:20  回复次数:8   
广度优先搜索问题,程序运行时终止,求帮忙看下哪里的错误?
题目描述
两个人约好一起吃饭。他们俩只能向上,下,左,右移动到相邻的地方,每走一步花费11分钟,找出两个人路上耗时之和最短的吃饭的地方。

输入
输入包含多组数据。
每组数据包括,两个数字n,m。(2<=n,m<=200)。
接下来n行,每行m个字母。
‘Y’ 表示第一个人的位置
‘M’ 表示第二个人的位置
‘#’ 表示墙
‘.’ 表示路
‘@’ 表示可以吃饭的地方


输出
每组数据输出他们到达同一个吃饭地点消耗的总时间的最小值。数据保证他们总能相见。


样例输入
4 4
Y.#@
....
.#..
@..M
4 4
Y.#@
....
.#..
@#.M
5 5
Y..@.
.#...
.#...
@..M.
#...#
样例输出
66
88
66

代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char a[200][200],visited[200][200];
struct step{
    int x;
    int y;
    int steps;
}st;
struct step s[40000];
int f(char a[][200],int n,int m,struct step *s,int x0,int y0,int x1,int y1){
    memset(s,0,sizeof(struct step)*10);
    memset(visited,0,sizeof(visited));
    struct step *head,*tail,*tail0;
    s[0].x=x0;
    s[0].y=y0;
    s[0].steps=0;
    visited[x0][y0]=1;
    head=s;
    tail=s+1;
    int k=1;
    while((tail-head)!=0){
        if((*head).x==x1 && (*head).y==y1){
            return (*head).steps;
        }
        tail0=tail;
        for(int i=0;i<4;i++){
            if(i==0){
                st.x=(*head).x+1;
                st.y=(*head).y;
            }
            else if(i==1){
                st.x=(*head).x-1;
                st.y=(*head).y;
            }
            else if(i==2){
                st.x=(*head).x;
                st.y=(*head).y+1;
            }
            else if(i==3){
                st.x=(*head).x;
                st.y=(*head).y-1;
            }
            if(st.x>=0 && st.x<n && st.y>=0 && st.y<m && a[st.x][st.y]!='#' && visited[st.x][st.y]==0){
                st.steps=k;
                visited[st.x][st.y]=1;
                *tail=st;
                tail++;
            }
        }
        if(tail0==tail) return 0;
        else{
          head++;
          k++;
        }
    }
    return 0;
}
int main(void){
    int n,m,i,j,id,jd,im,jm,tx[200],ty[200],txx=0,tyy=0,min,vd,vm;
    while((scanf("%d %d",&n,&m))!=EOF){
        min=802;
          for(i=0;i<n;i++){
                  scanf("%s",a[i]);
                  if(a[i][j]=='Y'){
                      id=i;
                      jd=j;
                  }
                  if(a[i][j]=='M'){
                      im=i;
                      jm=j;
                  }
                  if(a[i][j]=='@'){
                      tx[txx++]=i;
                      ty[tyy++]=j;
                  }
      }
        for(i=0;i<txx;i++){
            vd=f(a,n,m,s,id,jd,tx[i],ty[i]);
            vm=f(a,n,m,s,im,jm,tx[i],ty[i]);
            printf("vd=%d,vm=%d\n",vd,vm);
            if(vd!=0 && vm!=0)
              min=((min>(vd+vm))?(vd+vm):min);
        }
        printf("%d\n",min*11);
    }
    return 0;
}
         
2018-05-25 16:35
青蝶
Rank: 2
等 级:论坛游民
帖 子:127
专家分:26
注 册:2018-2-4
  得分:0 
基本思路是把队列用一个结构体数组表示,后入先出,指针head表示当前位置,指针tail表示最后存放的位置。
2018-05-25 16:37
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:48
帖 子:4932
专家分:13916
注 册:2016-10-22
  得分:10 
回复 2楼 青蝶
其实可以试试一下先搜出所有饭店离Y距离和离M的距离~
最后求和的时候取距离之和最少的那一次就可以了,也就是说广搜两次就行了

或者更直接可以分别用一个队列保存Y和M走过的状态,说直接一点就是M和Y一步一步轮流广搜,有交集的第一个饭店既是解~

[此贴子已经被作者于2018-5-25 16:52编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-25 16:47
lin5161678
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:8
帖 子:401
专家分:1474
注 册:2011-12-3
  得分:10 
程序代码:
          for(i=0;i<n;i++){
                  scanf("%s",a[i]);
                  if(a[i][j]=='Y'){
                      id=i;
                      jd=j;
                  }
                  if(a[i][j]=='M'){
                      im=i;
                      jm=j;
                  }
                  if(a[i][j]=='@'){
                      tx[txx++]=i;
                      ty[tyy++]=j;
                  }
      }

i 的值 从0到n
没问题
j 的值 ???GG
a[i][j] 错了
2018-05-25 17:33
青蝶
Rank: 2
等 级:论坛游民
帖 子:127
专家分:26
注 册:2018-2-4
  得分:0 
回复 4楼 lin5161678
谢谢大佬,改了以后函数好像也有问题,检查的时候在程序里输出了每一次vd和vm的值,是这样:  
4 4
Y.#@
....
.#..
@..M
vd=1,vm=0
vd=0,vm=0
vd=0,vm=0
8822
2018-05-25 19:08
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:48
帖 子:4932
专家分:13916
注 册:2016-10-22
  得分:0 
回复 5楼 青蝶
printf("vd=%d,vm=%d\n",vd,vm);
程序里面不是有这个东西么,去掉就可以了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-25 19:24
青蝶
Rank: 2
等 级:论坛游民
帖 子:127
专家分:26
注 册:2018-2-4
  得分:0 
回复 6楼 九转星河
不是,我没说清楚,那个是我加进去检查哪里有错用的,因为最后输出的结果不对。
2018-05-25 19:58
九转星河
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:长长久久
等 级:版主
威 望:48
帖 子:4932
专家分:13916
注 册:2016-10-22
  得分:0 
回复 7楼 青蝶
函数里面的可能我也看不出什么了,毕竟每个人的理解方式都或许不一样,看一些简单而正确的还好,但看一些复杂而且还有bug的那就难说了,我就是按我三楼那种思路来理解的~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-25 20:11
青蝶
Rank: 2
等 级:论坛游民
帖 子:127
专家分:26
注 册:2018-2-4
  得分:0 
回复 8楼 九转星河
好的,谢谢大佬~
2018-05-26 08:56







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

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