题目链接：https://vjudge.net/contest/184966#problem/A
题目大意：
走迷宫。从某个方向进入某点，优先走左或是右。如果左右都走不通，再考虑向前。绝对不能往后走，即使没走过。
解题思路：
重点是定义vis数组，每个点的四个方向都走过，这个点才算vis完了。……不过我还是没想明白，为什么能够想到要这样定义vis数组，应该题目做多了就知道了吧。
其它要注意的点就是如何实现优先左右转弯的功能。
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define N 85
int map[N][N], mmin, flag, n, m, vis[N][N][];
char str[N][N];
typedef struct node {
int x, y;
int father;//记录方向
int step;//记录步数
}node; int bfs(int x, int y)
{
int k[][] = { ,,-,,,-,, };
int nx, ny, xi, yi, x1, y1, x2, y2;
node nextq, nowq;
memset(vis, , sizeof(vis));//初始化标记数组
queue<node>Q;
flag = ;//标记是否能够成功到达
nowq.father = -;//起点的方向是-1，区别其它点
nowq.x = x;
nowq.y = y;
nowq.step = ;//初始化起点
vis[x][y][] = , vis[x][y][] = ;//起点标记为已经走过
vis[x][y][] = , vis[x][y][] = ;
Q.push(nowq);//将起点加入队列
while (!Q.empty())
{
nowq = Q.front();
Q.pop();
if (nowq.x == || nowq.y == || nowq.x == n - || nowq.y == m - )//到达出口，因为map的边界上只有一个为'.',且该点为出口
{
if (str[nowq.x][nowq.y] != '#')
flag = ;//能够成功到达
return nowq.step;
}
for (int i = ; i < ; i++)
{
nx = nowq.x + k[i][];
ny = nowq.y + k[i][];
if (nx < || ny < || nx > n - || ny > m - || str[nx][ny] == '#' || vis[nx][ny][i])
continue; //不能越界，不能是墙，不能已经是访问过的点
nextq.x = nx;
nextq.y = ny;
nextq.father = i;//记录父点到当前点的方向
nextq.step = nowq.step + ;//步数加1
if (nowq.father % == i % )
{
if (nowq.father == i)
{
x1 = nowq.x + k[(i + ) % ][];
y1 = nowq.y + k[(i + ) % ][];
x2 = nowq.x + k[(i - + ) % ][];
y2 = nowq.y + k[(i - + ) % ][];
if (str[x1][y1] != '.'&&str[x2][y2] != '.')//如果当前位置左右两边都不能走即只能直走
{
vis[nx][ny][i] = ;//标记该方向为已经访问过
Q.push(nextq);
}
}
}
else
{
vis[nx][ny][i] = ;
Q.push(nextq);
}
}
}
return -;
}
int main()
{
int t, i, j, x, y;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
memset(str, , sizeof(str));
for (i = ; i < n; i++)
{
scanf("%s", str[i]);
for (j = ; j < m; j++)
{
if (str[i][j] == '@')//找到起点，存入x,y.
{
x = i;
y = j;
}
}
}
mmin = bfs(x, y);//返回步数
if (flag)//如果能到达出口。输出步数
printf("%d\n", mmin);
else
printf("-1\n"); //否则输出-1 }
return ;
}
2018-03-25