Description
One popular maze-walking strategy guarantees that the visitor will eventually find the exit. Simply choose either the right or left wall, and follow it. Of course, there’s no guarantee which strategy (left or right) will be better, and the path taken is seldom the most efficient. (It also doesn’t work on mazes with exits that are not on the edge; those types of mazes are not represented in this problem.)
As the proprieter of a cornfield that is about to be converted into a maze, you’d like to have a computer program that can determine the left and right-hand paths along with the shortest path so that you can figure out which layout has the best chance of confounding visitors.
Input
Exactly one ‘S’ and one ‘E’ will be present in the maze, and they will always be located along one of the maze edges and never in a corner. The maze will be fully enclosed by walls (‘#’), with the only openings being the ‘S’ and ‘E’. The ‘S’ and ‘E’ will also be separated by at least one wall (‘#’).
You may assume that the maze exit is always reachable from the start point.
Output
Sample Input
2 8 8 ######## #......# #.####.# #.####.# #.####.# #.####.# #...#..# #S#E#### 9 5 ######### #.#.#.#.# S.......E #.#.#.#.# #########
Sample Output
37 5 5 17 17 9
题意：
给你个图，‘.’能走，问你从s点到e点，左转优先和右转优先还有两点最近距离分别是多少。
很明显，前两个答案是dfs，最后一个是bfs。
这个题的坑点就是在在于方向上的判别，我们需要给dfs时的点加一个状态，来表示它是什么方向，从而判断它的左右。
ps：附上一些样例，可以自己测一下。代码在最后面。
Input:
7
8 8
########
#……#
#.####.#
#.####.#
#.####.#
#.####.#
#…#..#
#S#E####
9 5
#########
#.#.#.#.#
S…….E
#.#.#.#.#
#########
3 3
###
S.#
#E#
40 40
######################################E#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#………………………………..#
#S######################################
40 40
########################################
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..#
#………………………………..#
#S#E####################################
40 40
#E######################################
S………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
######################################.#
#………………………………..#
#………………………………..#
########################################
11 11
#S#########
#………#
#.#.#.#.#.#
#…#…#.#
#####.###.#
#…#.#…#
#.#…#.#.#
#..##.#…#
#.#.#.###.#
#…#.#…#
#####E#####
=======================================================
Output:
37 5 5
17 17 9
3 3 3
77 77 77
1481 5 5
3 1483 3
47 45 15
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int a, b, sx, sy, ex, ey, qsfw, qsfw2;
int ans1 = 2323333, ans2 = 233333, ans3 = 233333, lsans = 1;
char map[50][50];
bool used[50][50];
bool flag = 0;
int xx[16] = {0, -1, 0, 1, 0, -1, 0, 1, 0};
int yy[16] = {0, 0, 1, 0, -1, 0, 1, 0, -1};
int xx1[16] = {0, 1, 0, -1, 0, 1, 0, -1, 0};
int yy1[16] = {0, 0, 1, 0, -1, 0, 1, 0, -1};
struct qer
{
int x, y, c;
};
queue <qer> q;
void dfs1(int x, int y, int fw)
{
//cout << x << " " << y << " " << fw << endl;
//system("pause");
if (x == ex && y == ey)
{
//cout <<"233"<<endl;
ans1 = min(ans1, lsans);
flag = 1;
return ;
}
int lx, ly, ls = 0;
for (int i = (fw+3)%4+1; i <= (fw+3)%4+4; i++)
{
ls = i;
lx = x + xx[i];
ly = y + yy[i];
//cout << lx << " " <<ly << " " << map[lx][ly] << endl;
if (1 <= lx && lx <= b && 1 <= ly && ly <= a && map[lx][ly] != '#' )
{
if (i > 4)
ls -= 4;
//used[lx][ly] = 1;
lsans++;
if (flag)
return;
dfs1(lx, ly, ls-1);
lsans++;
}
}
}
void dfs2(int x, int y, int fw)
{
//cout << x << " " << y << " " << fw << endl;
//system("pause");
if (x == ex && y == ey)
{
ans2 = min(ans2, lsans);
flag = 1;
return ;
}
int lx, ly, ls = 0;
for (int i = (fw+3)%4+1; i <= (fw+3)%4+4; i++)
{
if (flag)
return;
ls = i-1;
lx = x + xx1[i];
ly = y + yy1[i];
//cout << lx << " " <<ly << " " << map[lx][ly] << endl;
if (1 <= lx && lx <= b && 1 <= ly && ly <= a && map[lx][ly] != '#')
{
if (i > 4)
ls -= 4;
//used[lx][ly] = 1;
lsans++;
dfs2(lx, ly, ls);
lsans++;
}
}
}
void bfs(int x, int y)
{
while (!q.empty())
{
q.pop();
}
used[x][y] = 1;
q.push((qer){x, y, 1});
while (!q.empty())
{
qer ls2 = q.front();
q.pop();
if (ls2.x == ex && ls2.y == ey)
{
ans3 = ls2.c;
return;
}
for (int i = 1; i <= 4; i++)
{
int lx = ls2.x + xx[i];
int ly = ls2.y + yy[i];
if (1 <= lx && lx <= b && 1 <= ly && ly <= a && map[lx][ly] != '#' && !used[lx][ly])
{
used[lx][ly] = 1;
q.push((qer){lx, ly, ls2.c+1});
}
}
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
lsans = 1;
scanf("%d%d", &a, &b);
for (int i = 1; i <= b; i++)
scanf("%s", map[i]+1);
ans1 = 233333, ans2 = 233333, ans3 = 233333;
for (int i = 1; i <= b; i++)
{
for (int j = 1; j <= a; j++)
{
if (map[i][j] == 'S')
sx = i, sy = j;
if (map[i][j] == 'E')
ex = i, ey = j;
}
}
if (sx == 1)
qsfw = 2;
else if (sx == b)
qsfw = 0;
else if (sy == 1)
qsfw = 1;
else
qsfw = 3;
if (sx == 1)
qsfw2 = 4;
else if (sx == b)
qsfw2 = 2;
else if (sy == 1)
qsfw2 = 3;
else
qsfw2 = 1;
//printf("%d %d %d %d %d\n", sx, sy, ex, ey, qsfw);
memset(used, 0, sizeof(used));
flag = 0;
dfs1(sx, sy, qsfw);
lsans = 1;
flag = 0;
memset(used, 0, sizeof(used));
dfs2(sx, sy, qsfw2);
lsans = 1;
memset(used, 0, sizeof(used));
bfs(sx, sy);
if (ans1!=233333)
cout << ans1 << " ";
else
cout << " ";
if (ans2!=233333)
cout << ans2 << " ";
else
cout << " ";
if (ans3!=233333)
cout << ans3 << " ";
else
cout << " ";
cout << endl;
}
return 0;
}