本文主要是介绍hdu 4375 Programmable Robot，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=4375
网上还很少有人写这道题目的结题报告的，就把我自己能理解的写下来，我是看到 http://www.mzry1992.com/blog/miao/2012-multi-university-training-contest-8.html 博客才慢慢理解的。写的很好，Orz
首先通过分析：
1） 向前走时不能够改变方向的，所以对于题目所给出的指令的某个位置是方向是确定的
2）某个点坐标(x,y)有东南西北四个状态，如果才能表示每个状态的好与坏呢？注意到：一个点在某一时刻处于某种方向，一定比其后还是在改点处于这种方向时更优，因为只要机器人不向前行走，就一定能达到后面的状态。从而我们就能找到状态的优劣，dist[x][y][dir] 表示在（x,y）面向dir方向的最近的指令，bfs即可
3）优化：每个点的状态到另外个状态，有两种方式： 1 前进 ； 2 原地改变方向 具体看代码实现吧！
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;char s[1000100],mp[1100][1100];
int n,m,l,sx,sy,ex,ey,next[1000100][4],pos[4],dir[1000100],dist[1100][1100][4];
const int step[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
/*0
3 12
*/vector<pair<int,int> > Q[1000100];bool BFS()
{for (int i = 0;i <= l;i++)Q[i].clear();for (int i = 0;i < n;i++)for (int j = 0;j < m;j++)for (int k = 0;k < 4;k++)dist[i][j][k] = 2*l;Q[0].push_back(make_pair(sx,sy));dist[sx][sy][0] = 0;for (int dis = 0;dis <= l;dis++)for (int pi = 0;pi < Q[dis].size();pi++){pair<int,int> now = Q[dis][pi];if (now.first == ex && now.second == ey) return true;for (int i = 0;i < 4;i++)if (next[dis][i] != -1){if (dist[now.first][now.second][i] == 2*l){dist[now.first][now.second][i] = next[dis][i];Q[next[dis][i]].push_back(now);}}int v = dir[dis];pair<int,int> nxt = make_pair(now.first+step[v][0],now.second+step[v][1]);if (nxt.first < 0 || nxt.first >= n || nxt.second < 0 || nxt.second >= m || mp[nxt.first][nxt.second] == '#')continue;if (dist[nxt.first][nxt.second][v] == 2*l){dist[nxt.first][nxt.second][v] = dis;Q[dis].push_back(nxt);}}return false;
}void calcnext()
{dir[0] = 0;for (int i = 1;i <= l;i++)if (s[i-1] == 'L')dir[i] = (dir[i-1]+3)%4;elsedir[i] = (dir[i-1]+1)%4;for (int i = 0;i < 4;i++)pos[i] = -1;pos[dir[l]] = l;for (int i = l-1;i >= 0;i--){pos[dir[i]] = i;// next[i][0] = pos[(dir[i]+3)%4];// next[i][1] = pos[(dir[i]+1)%4];for(int j=0;j<4;j++)next[i][j]=pos[j];}
}int main()
{//freopen("1006.in","r",stdin);// freopen("1006_2.out","w",stdout);while (scanf("%d%d%d",&n,&m,&l) != EOF){scanf("%s",s);calcnext();for (int i = 0; i < n; i++){scanf("%s",mp[i]);for (int j = 0; j < m; j++)if (mp[i][j] == 'S')sx = i,sy = j;else if (mp[i][j] == 'E')ex = i,ey = j;}if (BFS())puts("Yes");elseputs("No");}return 0;
}
这篇关于hdu 4375 Programmable Robot的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
