一个有几个小坑的bfs
题目很长，但并不复杂，大概总结起来有这么点。
有t组输入
每组输入n, m, p。表示一个n*m的地图，每p秒按键会右移一次（这个等会儿再讲）。
然后是地图的输入。其中'@'为起点，'$'为终点，'.'为通路，'*'为不通。
问从起点到终点最少需要多久？
一眼看去，裸的bfs嘛，10*10的地图，简单！
不过还是连错4次……
注意！
每一秒有4种操作，注意，不是三种，1. 光标左移，2. 光标右移，3. 按照光标方向行走，4. 不动（尤其是这一个）。
所谓光标左移，右移，因为题目中给出了光标（在图上，共4个方向），每次改变的移动方向只能是当前光标选择的方向的左右两个。而行走只能按照光标所指的方向。
另外每过p秒，方向会变化（初始四个方向的顺序为左右上下，p秒后变成右上下左，再过p秒后变为上下左右）。
废话说完，上代码——
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std; const int N = ; struct node
{
int x, y, dis, step;
}; int go[][] = {{, -}, {, }, {-, }, {, }}; int t;
int n, m, P;
char mp[N][N];
bool v[N][N];
bool vv[N][N][]; int change(int a)
{
switch(a)
{
case :
return ;
case :
return ;
case :
return ;
case :
return ;
}
} void bfs()
{
node p;
bool k = ;
for(int i = ; i < n; i++)
{
for(int j = ; j < m; j++)
{
if(mp[i][j] == '@')
{
p.x = i;
p.y = j;
k = ; break;
}
}
if(k) break;
}
p.dis = ;
p.step = ;
vv[p.x][p.y][] = ; queue<node> que;
que.push(p);
while(!que.empty())
{
node p = que.front();
que.pop(); int xx = p.x+go[p.dis][];
int yy = p.y+go[p.dis][];
if(xx >= && xx < n && yy >= && yy < m)
{
if(v[xx][yy] == )
{
if(mp[xx][yy] == '.')
{
v[xx][yy] = ;
node q;
q.x = xx;
q.y = yy;
q.step = p.step+;
q.dis = p.dis;
if(q.step%P == )
{
q.dis = change(q.dis);
vv[xx][yy][q.dis] = ;
}
que.push(q);
}
else if(mp[xx][yy] == '$')
{
printf("%d\n", p.step+);
return;
}
}
} if((p.step+)%P == ) {p.dis = change(p.dis);} node q;
q.x = p.x;
q.y = p.y;
q.step = p.step+; q.dis = p.dis+;
q.dis %= ;
if(vv[q.x][q.y][q.dis] == )
{
que.push(q);
vv[q.x][q.y][q.dis] = ;
} q.dis = p.dis+;
q.dis %= ;
if(vv[q.x][q.y][q.dis] == )
{
que.push(q);
vv[q.x][q.y][q.dis] = ;
} q.dis = p.dis;
if(vv[q.x][q.y][q.dis] == )
{
que.push(q);
vv[q.x][q.y][q.dis] = ;
}
}
printf("YouBadbad\n");
} int main()
{
//freopen("test.txt", "r", stdin);
scanf("%d", &t);
while(t--)
{
memset(mp, , sizeof(mp));
memset(v, , sizeof(v));
memset(vv, , sizeof(vv));
scanf("%d%d%d", &n, &m, &P);
for(int i = ; i < n; i++)
{
scanf("%s", mp[i]);
}
bfs();
}
}