首页 > 代码库 > poj3083 Children of the Candy Corn
poj3083 Children of the Candy Corn
这道题有深搜和广搜。深搜还有要求，靠左或靠右。下面以靠左为例，可以把简单分为上北，下南，左西，右东四个方向。向东就是横坐标i不变，纵坐标j加1（i与j其实就是下标）。其他方向也可以这样确定。通过上一步方向可以确定下一步应该从哪个方向开始搜。比如说，是向北走的，就必须先搜西，西不可以走，再搜北，如果北还不可以走，再搜东，最后才是南。其他方向的情况也可以这样推出来。最后走到E点完成了。广搜就是最基础的广搜。这道题做了将近10个小时。中途曾几次准备放弃，但最后还是坚持做完了。
#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<algorithm>using namespace std;char maze[40][40];int n,m,ex,ey,sx,sy,flag,s,cx,cy,df;int dlx[7]={0,1,0,-1,0,1,0};int dly[7]={1,0,-1,0,1,0,-1};int drx[7]={0,-1,0,1,0,-1,0};int dry[7]={1,0,-1,0,1,0,-1};int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int isin(int x,int y){ return x>=0&&x<n&&y>=0&&y<m;}void lfs(int i,int j){ int x,y,k; if(flag) return ; if(i==ex&&j==ey) {flag=1;} else for(k=df;k<7&&!flag;k++) { cx=dlx[k]; cy=dly[k]; x=i+dlx[k]; y=j+dly[k]; if(isin(x,y)&&maze[x][y]!=‘#‘){ s++; if(cx==1) df=0; //往南的，先搜东 else if(cx==-1) df=2; //往北的，先搜西 else if(!cx){ if(cy==1) df=3; //往东的，先搜北 else df=1; } //printf("(%d %d) ",x,y); lfs(x,y); } }}void rfs(int i,int j){ int x,y,k,d; if(flag) return ; if(i==ex&&j==ey) {flag=1;} else for(k=df;k<7&&!flag;k++) { cx=drx[k]; cy=dry[k]; x=i+drx[k]; y=j+dry[k]; if(isin(x,y)&&maze[x][y]!=‘#‘){ s++; if(cx==1) df=2; //往南的，先搜西 else if(cx==-1) df=0; //往北的，先搜东 else if(!cx){ if(cy==1) df=3; //往东的，先搜南 else df=1; } //printf("(%d %d) ",x,y); rfs(x,y); } }}struct node{ int dis,row,col;};queue<node> q;void bfs(){ int x,y,k,d,i,j; node t; while(!q.empty()) { t=q.front(); q.pop(); d=t.dis; i=t.row; j=t.col; for(k=0;k<4;k++) { x=i+dx[k]; y=j+dy[k]; if(maze[x][y]!=‘#‘&&isin(x,y)){ if(x==ex&&y==ey){ s=d+1; return ; } else{ t.dis=d+1; t.row=x; t.col=y; q.push(t); maze[x][y]=‘#‘; } } } }}int main(){ int ca,i,j; scanf("%d",&ca); while(ca--) { scanf("%d%d",&m,&n); getchar(); for(i=0;i<n;i++) gets(maze[i]); for(i=0;i<n;i++){ for(j=0;j<m;j++){ if(maze[i][j]==‘S‘){ sx=i;sy=j; maze[sx][sy]=‘#‘; } else if(maze[i][j]==‘E‘){ ex=i;ey=j; maze[ex][ey]=‘.‘; } } } flag=0; s=1; if(!sy) df=3; else if(!sx) df=0; else if(sy==m-1) df=1; else if(sx==n-1) df=2; lfs(sx,sy); if(!sy) df=3; else if(!sx) df=0; else if(sy==m-1) df=1; else if(sx==n-1) df=2; cout<<s<<‘ ‘; flag=0; s=1; rfs(sx,sy); cout<<s<<‘ ‘; while(!q.empty()) q.pop(); node p; p.dis=1; p.row=sx; p.col=sy; q.push(p); s=1; bfs(); cout<<s<<endl; } return 0;}
poj3083 Children of the Candy Corn
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。