本文主要是介绍POJ 3083 *** Children of the Candy Corn，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意:走迷宫，求一直靠墙向左走和靠墙向右走以及最短路径的长度。
想法:我真是智商感人，写个dfs和bfs都错误多多。一直也没理解到靠墙向左走和靠墙向右走是怎么回事，原来靠墙左走是顺时针走，靠墙右走为逆时针，同时下一点的初始行走方向依赖于前一步到达该点的行走方向。同时从起点到终点向右走等同于从终点到起点向左走。对了，以后保持每天至少ac两道题吧。
代码如下：
<div>#pragma warning(disable:4996)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<stack>
#include<queue>
#include<cstring>
#include<sstream>
#include<set>
#include<string>
#include<iterator>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;</div><div>
</div><div>char maze[50][50];
int mark[50][50];
int dir[4][2] = { {1,0},{0,-1},{-1,0},{0,1} };//顺时针的向左路线
int n, w, h, leftcnt, rightcnt, totalcnt, flag;
struct Position {
int x, y;
int dd;
};
Position start, eend;</div><div>//深搜，寻找向左向右长度
</div><div>void dfs(Position start,Position eend,int d) {
if (start.x == eend.x&&start.y == eend.y) { flag = 0; totalcnt++; return; }//寻找是否到达终点
int nowd = d;//初始行走方向
while (nowd < 4+d&&flag) {
Position temp = { start.x + dir[nowd % 4][0], start.y + dir[nowd % 4][1] };//行走
if (temp.x>0 && temp.x <= h&& temp.y > 0 && temp.y <= w&&maze[temp.x][temp.y] != '#'&&flag) {//到达新的一点
totalcnt++;
temp.dd = (nowd + 3) % 4;//新点的初始行走方向为到该点的方向逆时针90°
dfs(temp, eend, temp.dd);//寻找下一个点
if (!flag)return;//如果上一个dfs已经找到终点则return
}
nowd++;
}
}</div><div>//广搜找最小路径
</div><div>void bfs() {
totalcnt = 0;
int flag = 1;
memset(mark, 0,sizeof(mark));
Position now;
queue<Position>path;
path.push(start);
mark[start.x][start.y] = 1;
while (!path.empty()&&flag) {
now = path.front();
path.pop();
for (int i = 0; i < 4; ++i) {
int x = now.x + dir[i][0], y = now.y + dir[i][1];
if (x == eend.x&&y == eend.y) { flag = 0; break; }
if (x>0&&x<=h&&y>0&&y<=w&&!mark[x][y] && maze[x][y] == '.') {
mark[x][y] = mark[now.x][now.y] + 1;
Position temp = { x,y };
path.push(temp);
}
}
}
totalcnt = mark[now.x][now.y]+1;
}</div><div>
</div><div>int main(void) {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n;
while (n--) {
cin >> w >> h;
for (int i = 1; i <= h; ++i)
for (int j = 1; j <= w; ++j) {
cin >> maze[i][j];
if (maze[i][j] == 'S')
start.x = i, start.y = j;
else if (maze[i][j] == 'E')
eend.x = i, eend.y = j;
}
totalcnt = 0;
flag = 1;
dfs(start, eend,0 );//初始方向因为只有一个点的方向可以走，于是设置为0也ok
leftcnt = totalcnt;
totalcnt = 0;
flag = 1;
dfs(eend, start, 0);
rightcnt = totalcnt;
bfs();
cout << leftcnt<<" "<<rightcnt<<" "<<totalcnt << endl;
}
return 0;
}</div>这篇关于POJ 3083 *** Children of the Candy Corn的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
