BYR Achieve · 镜像论坛

【问题】大家好，遇见一道深度优先搜索...WA求助

2017/12/16镜像同步4 回复

这道题的备注是dfs,但是可能是我菜菜的深搜做的不好，深搜总是超时，所以我的现状是只能用dfs解决类似8皇后，2n皇后那种问题，对于求最优解的问题（走迷宫，最大最小连通块）还都是用结构体+队列实现的。这又是一道类似走迷宫的题但是加了一点特殊条件，我仍然用队列做，但是就过不去了。[ema1] 求帮助。。。以下是题目描述孙涛的爱好是Universe7，见面会上坐在旁边的我被秀一脸，现在就让他们在一张召唤师峡谷里面，孙涛想要去嘿嘿嘿Universe7~ 但是通往成功的道路总有阻碍，中间有一些山地不能直接走过去。但这些山地会忽隐忽现，在走的步数是k的倍数的时候，山地会消失，其他时间还在那里。（比如假设k=2，当你走到n*k步时，山地会消失）用“.”表示可以走的路，“#”表示山地。孙涛用S表示，Universe7用U表示。每次孙涛可以上下左右移动，Universe7乖巧不动。输入第一行是T，表示T组数据。每组后面跟三个整数r,c (1 <= r , c <= 100), and k(2 <=k <= 10)。 r表示峡谷的长，c表示峡谷的宽。然后是峡谷的描述。输出对于每组数据，如果孙涛能嘿嘿嘿到Universe7，输出最小的步数，否则输出“once more!”。样例输入1 1 6 6 2 ...S.. ...#.. .#.... ...#.. ...#.. ..#U#. 样例输出1 7 贴上WA的代码[ema23] #include<iostream> #include<cstring> #include<vector> #include<string> #include<queue> using namespace std; int a[4]={-1,0,1,0}; int b[4]={0,1,0,-1}; int r,c,k; struct point { int x,y,step;//x,y为坐标，step是步数 }; int search(); queue <point> p; queue <point> blank; char map[101][101]; int sign[101][101];//记录走过的点，走过则为1 int main() { int T; cin>>T; while(T--) { memset(sign,0,sizeof(sign));//清空sign cin>>r>>c>>k; for(int i=0;i<r;++i) for(int j=0;j<c;++j) { cin>>map[i][j]; if(map[i][j]=='S')//发现起点就让起点的坐标，步数进队 { point temp0; temp0.x=i;temp0.y=j;temp0.step=0; p=blank;//清空队列 p.push(temp0);//入队 sign[i][j]=1;//走过标记为1 } } search();//搜索 } return 0; } int search() { while(!p.empty())//队非空 { point temp; temp=p.front();//取队首 if(map[temp.x][temp.y]=='U')//当刚好是终点使输出，return 0终止search { cout<<temp.step<<endl; return 0; } for(int i=0;i<4;++i)//上下左右依次差 { if((temp.x+a[i]>=0)&&(temp.x+a[i]<r) &&(temp.y+b[i]>=0)&&(temp.y+b[i]<c))//判断是否会越界 { point temp2; temp2.x=temp.x+a[i];temp2.y=temp.y+b[i];temp2.step=temp.step+1; if((temp2.step%k)==0)//如果满足障碍消失条件 { if(sign[temp2.x][temp2.y]==0)//如果此点没走过 { sign[temp2.x][temp2.y]=1;//占领此点 p.push(temp2);//入队 } } else//不满足障碍消失的条件 { if((sign[temp2.x][temp2.y]==0)&&(map[temp2.x][temp2.y]!='#')) //如果此点没走过且此点处没有障碍物 { sign[temp2.x][temp2.y]=1;//占领这点 p.push(temp2);//入队 } } } } p.pop();//出队 } if((r==1)&&(c==1)) cout<<"0"<<endl;//当队空时也没找到终点 else cout<<"once more!"<<endl; return 0; } 求助大家了，谢谢了[ema23] 附件(1.5KB)

订阅后，新回复会通过你的通知中心匿名送达。