本文主要是介绍POJ 3083Children of the Candy Corn(DFS*2+BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：http://poj.org/problem?id=3083
这道题整体思路并不难，但一些细节方面有点难想。。主要是容易写的太麻烦，太乱。。虽然我的代码也比较长，但是思路还是挺清晰的（基本就是把上一段的复制下来稍微改改。。）。但是有些细节方面一开始想错了，导致调试了很长时间。主要思路是记录4个方向然后改变方向走。
题目意思是输出往左绕的步数与往右绕的步数，还有最短步数。前两个用DFS做更容易些。最短步数当然用的BFS。。
代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>using namespace std;
char mp[50][50];
int vis[50][50], n, m, ans1, ans2;
struct node
{int x, y, ans;
};
int jx[]= {1,0,-1,0};
int jy[]= {0,-1,0,1};
void dfs1(int x, int y, int z)
{int a, b, i;z=z==1?4:z-1;if(mp[x][y]=='E'){printf("%d ",ans1);return ;}for(i=0; i<4; i++){if(z==1){a=x+jx[0];b=y+jy[0];if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]!='#'){ans1++;dfs1(a,b,1);break;}else{z=2;}}else if(z==2){a=x+jx[1];b=y+jy[1];if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]!='#'){ans1++;dfs1(a,b,2);break;}else{z=3;}}else if(z==3){a=x+jx[2];b=y+jy[2];if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]!='#'){ans1++;dfs1(a,b,3);break;}else{z=4;}}else if(z==4){a=x+jx[3];b=y+jy[3];if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]!='#'){ans1++;dfs1(a,b,4);break;}else{z=1;}}}
}
void dfs2(int x, int y, int z)
{int a, b, i;z=z==4?1:z+1;if(mp[x][y]=='E'){printf("%d ",ans2);return ;}for(i=0; i<4; i++){if(z==1){a=x+jx[0];b=y+jy[0];if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]!='#'){ans2++;dfs2(a,b,1);break;}else{z=4;}}else if(z==2){a=x+jx[1];b=y+jy[1];if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]!='#'){ans2++;dfs2(a,b,2);break;}else{z=1;}}else if(z==3){a=x+jx[2];b=y+jy[2];if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]!='#'){ans2++;dfs2(a,b,3);break;}else{z=2;}}else if(z==4){a=x+jx[3];b=y+jy[3];if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]!='#'){ans2++;dfs2(a,b,4);break;}else{z=3;}}}
}
void bfs(int x, int y)
{int i;queue<node>q;node f1,f2;memset(vis,0,sizeof(vis));f1.x=x;f1.y=y;f1.ans=1;vis[x][y]=1;q.push(f1);while(!q.empty()){f1=q.front();q.pop();if(mp[f1.x][f1.y]=='E'){printf("%d\n",f1.ans);return ;}for(i=0; i<4; i++){f2.x=f1.x+jx[i];f2.y=f1.y+jy[i];if(f2.x>=0&&f2.x<n&&f2.y>=0&&f2.y<m&&!vis[f2.x][f2.y]&&mp[f2.x][f2.y]!='#'){f2.ans=f1.ans+1;vis[f2.x][f2.y]=1;q.push(f2);}}}
}
int main()
{int t, i, j;scanf("%d",&t);while(t--){scanf("%d%d",&m,&n);for(i=0; i<n; i++){scanf("%s",mp[i]);}for(i=0; i<n; i++){for(j=0; j<m; j++){if(mp[i][j]=='S'){break;}}if(j!=m)break;}int z;if(i==0)z=1;else if(j==m-1)z=2;else if(i==n-1)z=3;elsez=4;ans1=1;ans2=1;dfs1(i,j,z);dfs2(i,j,z);bfs(i,j);}return 0;
}
这篇关于POJ 3083Children of the Candy Corn(DFS*2+BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
