这道题是一道搜索题
但是 如果没有读懂或者 或者拐过弯 就很麻烦
最多26个火车 那么每一个周期 （人走一次 车走一次） 就要更改地图 的状态 而且操作复杂 容易超时 出错
利用相对运动
计周期为 人向上或向下或不动一步 + 向右三步
这样就变为走迷宫问题了
同样要注意
1、去重数组 或者 将以前访问过的点置为其他符号 避免重复访问
2、还有 因为 每次是三步三步的往右走 所以最后的边界可能不够 可以再扩充三列
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue> using namespace std; typedef pair<int, int> P; int T,t;
//bool vis[3][104];
char maze[][];
P start; bool check(int x ,int y)
{
if (x > || x < ) return false;
if (maze[x][y] != '.') return false;
return true;
}
bool bfs()
{
queue<P> que;
P crt = start;
crt.second++;
if (crt.second >= t) return true;
if (maze[crt.first][crt.second] == '.') que.push(crt);
while (!que.empty())
{
P crt = que.front();
que.pop();
for (int i = -; i < ; i++)
{
int tx = crt.first + i, ty = crt.second;
if ( !check(tx, ty) ) continue;
bool isSafe = true;
for (int j = ; j <= ; j++)
{
if (!check(tx, ty+j))
{
isSafe = false;
break;
}
}
if (isSafe)
{
if (ty+ >= t) return true;
else
que.push(P(tx, ty+));
}
}
maze[crt.first][crt.second] = 'A';//使用去重数组的话 内存超了 当访问完这个点以后 做标记 以后不再访问
}
return false;
}
int main()
{
freopen("in.txt", "r", stdin);
scanf("%d", &T);
int k;
while (T--)
{
scanf("%d%d", &t, &k);
//memset(vis, false, sizeof(vis));
for (int i = ; i < ; i++)
{
getchar();
for (int j = ; j < t; j++)
{
scanf("%c", &maze[i][j]);
if (maze[i][j] == 's')
{
start.first = i;
start.second = j;
}
}
for (int j = t; j < t+; j++)
{
maze[i][j] = '.';
}
}
if(bfs()) printf("YES\n");
else printf("NO\n");
}
return ;
}