Abbott‘s Revenge

/*
SAMPLE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0
NOSOLUTION
3 1 N 3 2
1 1 WL NR *
1 2 NL ER *
2 1 SL WR NFR *
2 2 SR EL *
0
END
*/
#include <iostream>
#include <cstring>
#include <queue>
#define MAX 9
using namespace std;
const char* dirs = "NESW"; // c字符串
const char* turns = "FLR";
struct Node{
int r,c,dir;
Node(int r=0, int c=0, int dir=0):r(r),c(c),dir(dir) {}
};
// have_edge[r][c][dir][turn]表示在r行c列面朝dir时，能否向turn方向转
int have_edge[MAX][MAX][4][3];
// 该组输入的名称
char name[20];
// 初始数据及第一步数据
int en_r,en_c,en_dir,out_r,out_c,en_r1,en_c1;
// 距离矩阵
int d[MAX][MAX][4];
Node p[MAX][MAX][4];
const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};
// strchr包含在C标准库<string.h>中，在str所指向的字符串中搜索第一次出现字符c的地址
int dir_id(char c){return strchr(dirs, c) - dirs;} // 地址作差，得到序号
int turn_id(char c){return strchr(turns, c) - turns;}
// 数据读取
int scan() {
int r, c;
char dt[4];
cin.getline(name, 20); // 从行中读取20个字符，将其传递给指针name
// 初始位置，初始朝向，终止位置
scanf("%d %d %c %d %d", &en_r, &en_c, &en_dir, &out_r, &out_c);
// 第一步
en_r1 = en_r + dr[dir_id(en_dir)];
en_c1 = en_c + dc[dir_id(en_dir)];
en_dir = dir_id(en_dir);
if (strcmp(name, "END") == 0)return 0;
while(scanf("%d",&r)){ // 首先读取r
if (r == 0)break;
// 然后如果r=0，那么就意味着输入结束
scanf("%d", &c);
// 接着读取c
while (scanf("%s", dt)) { // 读取朝向和变换的信息，读到空白为止
if (dt[0] == '*')break;
// 读到*就结束
int len = strlen(dt);
// 看看这个字符串的长度
int did = dir_id(dt[0]);
// 读取朝向
for (int i = 1; i < len; i++)
have_edge[r][c][did][turn_id(dt[i])] = 1; // 将可行的方式记录
}
}
return 1;
}
// 移动节点
Node walk(const Node& u, int turn){
// step1 读入进入当前点的朝向
int dir = u.dir;
// step2 旋转朝向
if(turn == 1) dir = (dir+3)%4;
if(turn == 2) dir = (dir+1)%4;
// step3 更新节点的参数
return Node(u.r + dr[dir], u.c + dc[dir], dir);
}
int inside(int r, int c) {
return r > 0 && r <= 9 && c > 0 && c <= 9;
}
void print_ans(Node u)
{
vector<Node> nodes;
while (1) {
nodes.push_back(u);
if (d[u.r][u.c][u.dir] == 0) break;
u = p[u.r][u.c][u.dir];
}
nodes.push_back(Node(en_r, en_c, en_dir));
//打印解，每行10个
int cnt = 0;
for (int i = (int)nodes.size() - 1; i >= 0; i--) {
if (cnt % 10 == 0) printf(" ");
printf(" (%d,%d)", nodes[i].r, nodes[i].c);//输出的时候不要带编码风格的空格，哭
if (++cnt % 10 == 0) printf("n");
}
if (nodes.size() % 10 != 0) printf("n");
}
void solve() {
queue<Node> q;
// 将内存中的内容全部设置为指定的值
memset(d, -1, sizeof(d));
Node u(en_r1, en_c1, en_dir);
d[en_r1][en_c1][en_dir] = 0;
q.push(u);
while (!q.empty()) {
u = q.front(); q.pop();
if (u.r == out_r && u.c == out_c) {
print_ans(u);
return;
}
for (int i = 0; i < 3; i++) {
Node v = walk(u, i); // 下一个点的信息
if (have_edge[u.r][u.c][u.dir][i] && inside(v.r, v.c) && d[v.r][v.c][v.dir] < 0) {
d[v.r][v.c][v.dir] = d[u.r][u.c][u.dir] + 1; // 距离增加
p[v.r][v.c][v.dir] = u;
// 记录当前点的父节点
q.push(v);
}
}
}
printf("No Solution Possiblen");
}
int main(int argc,const char* argv[]){
while (scan()) {
solve();
}
return 0;
}

关于图的一些信息，比如说每个点他们之间可不可通行，可以用邻接矩阵的样式表示。可以这样表示的还有他们的父亲矩阵。

最后

以上就是繁荣洋葱为你收集整理的Abbott‘s Revenge的全部内容，希望文章能够帮你解决Abbott‘s Revenge所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。