本文主要是介绍uva 10047 uva live 2035 The Monocycle bfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// uva 10047 uva live 2035 bfs
// 求最短的嘛，肯定先尝试bfs啦
// 确定状态，首先状态里面得有坐标x，y
// 还得有朝向，还得有颜色值
//
// 这样就是一个状态里面有着三种属性
// 每个状态都只要经历一次，再经历是没有任何意义的
// 用一个que的思维数组记录就行了。
// 按照方向爆搜，我先用f[i][j]记录的就是到
// 这一点的最小距离，但是怎么都过不了样例
// 突然明白了，如果只是这样记录最短距离，是不行的
// 因为每次从队列中取出的元素都有可能改变终点的状态
// 所以，应该在状态里面再记录一个属性，那就是时间
// 最后，注意两个样例之间要有空行啊。。。wa了一发
// 嗯，之后就过了。
// 嗯，继续练吧。。。。#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define ceil(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define gcd __gcd
#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))
#define popCount __builtin_popcountll
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const long double PI = acos(-1.L);template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; }
template<class T> inline T lowBit(const T& x) { return x&-x; }
template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; }
template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; }const int maxn = 30;
char mp[maxn][maxn];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int n,m;
char a[5][10] = {"GREEN","WHITE","BLUE","RED","BLACK"};
struct node {int x,y;int on;int color;int time;
};
int f[maxn][maxn];
bool que[26][26][5][6];
queue<node> q;
void init(){for (int i=0;i<n;i++)scanf("%s",mp[i]);
// memset(f,-1,sizeof(f));memset(que,0,sizeof(que));while(!q.empty()) q.pop();
}void print(){for (int i=0;i<n;i++){for (int j=0;j<m;j++){printf("%d ",f[i][j]);}puts("");}puts("");
}void solve(int kase){if (kase!=1)puts("");printf("Case #%d\n",kase);int ex,ey;for (int i=0;i<n;i++)for (int j=0;j<m;j++){if (mp[i][j]=='S'){q.push((node){i,j,0,0,0});que[i][j][0][0] = true;// f[i][j] = 0;}if (mp[i][j]=='T'){ex = i;ey = j;}}int time = -1;int cc = 0;while(!q.empty()){node x = q.front();// printf("%d %d %d %s\n",x.x,x.y,x.on,a[x.color]);q.pop();if (x.x==ex && x.y==ey && x.color==0){//time = //f[x.x][x.y];time = x.time;break;}for (int i=-1;i<=1;i++){int j = x.on + i;if (j==-1)//左转j = 3;if (j==4)//右转j = 0;if (i==0){//直走int tx = x.x + dx[j];int ty = x.y + dy[j];if (tx<0||tx>=n||ty<0||ty>=m) continue;if (mp[tx][ty]=='#') continue;if (!que[tx][ty][j][(x.color+1)%5]){//f[tx][ty] = f[x.x][x.y]+1;q.push((node){tx,ty,j,(x.color+1)%5,x.time+1});que[tx][ty][j][(x.color+1)%5] = true;}}else {//转弯的情况if (!que[x.x][x.y][j][x.color]){f[x.x][x.y]++;q.push((node){x.x,x.y,j,x.color,x.time+1});que[x.x][x.y][j][x.color] = true;}}}// que[x.x][x.y][x.on][x.color] = false;}//print();if (time == -1){printf("destination not reachable");}else {printf("minimum time = %d sec",time);}puts("");
// puts("");
}int main() {int kase = 0;//freopen("G:\\Code\\1.txt","r",stdin);while(scanf("%d%d",&n,&m)){if (!n&&!m)break;init();solve(++kase);}return 0;
}
这篇关于uva 10047 uva live 2035 The Monocycle bfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
