题目描述:
转载自:https://blog.csdn.net/h1021456873/article/details/54572767
题意:
给你一个转轮,有5种颜色,为了5中颜色的位置是确定的,为了方便处理我们用01234来表示绿,黑,红,蓝,白。*可以沿着它的方向滚动(只能是它当前的方向不能相反方向),每滚动一次会到达另一个格子,着地的颜色会改变,变了之前颜色的下一个,例如当前是绿色着地下一次就是黑色,依次是红蓝白。也可以原地转动(顺逆时针都可以),原地转动其实就是改变了*的滚动方向,原地转动每次能转90度。原地转动一次和滚动一次时间都是1秒。另外*有4个方向,上北下南左西又东。
思路: 开一个四维数组标记状态 f【x】【y】【d】【c】 在(x,y)点,方向为d,车轮的颜色为c的状态是否被标记过, 这个数组其实就是用来剪枝,避免陷入死循环!!!!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N = ;
char s[N][N];
struct node
{
int x,y,d,c,time;
};
queue<node>que;
int f[N][N][][];
int n,m;
int dx[]={,-,,},dy[]={-,,,};
node e;
int bfs()
{
int i,j,x,y,d,c;
while(!que.empty()){
node t = que.front();
que.pop();
if(t.x==e.x && t.y==e.y && t.c==) return t.time;
////////先考虑转向/////////////////////
c=t.c;
d=(t.d+)%;
if(!f[t.x][t.y][d][c]){
f[t.x][t.y][d][c]++;
que.push((node){t.x,t.y,d,c,t.time+});
// printf("%d %d %d %d %d\n",t.x,t.y,d,c,t.time+1);
}
d=(t.d-+)%;
if(!f[t.x][t.y][d][c]) {
f[t.x][t.y][d][c]++;
que.push((node){t.x,t.y,d,c,t.time+});
// printf("%d %d %d %d %d\n",t.x,t.y,d,c,t.time+1);
}
////////考虑向前走////////////////////
c=(t.c+)%;
x=t.x+dx[t.d],y=t.y+dy[t.d],d=t.d;
if(x<||x>=n||y<||y>=m||s[x][y]=='#') continue;
if(f[x][y][d][c]) continue;
f[x][y][d][c]++;
que.push((node){x,y,d,c,t.time+});
// printf("%d %d %d %d %d\n",x,y,d,c,t.time+1);
}
return -;
} int main()
{
node start;
int i,j,T=;
while(scanf("%d%d",&n,&m)!=EOF) {
if(n== && m==) break;
if(T) printf("\n");
T++;
while(!que.empty()) que.pop();
memset(f,,sizeof(f));
for(i=;i<n;i++) {
scanf("%s",s[i]);
for(j=;j<m;j++) {
if(s[i][j]=='S') start.x=i,start.y=j;
if(s[i][j]=='T') e.x=i,e.y=j;
}
}
start.d=,start.c=,start.time=;
f[start.x][start.y][start.d][start.c]=;
que.push(start);
int ans=bfs();
printf("Case #%d\n",T);
if(ans<) printf("destination not reachable\n");
else printf("minimum time = %d sec\n",ans);
}
return ;
}