#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 10;
const char* dirs = "NESW";
const char* turn = "FLR";
int dir_id(char c) { return strchr(dirs, c) - dirs; }/*返回方向的排列数,将方向转换为数字使用--数组*/
int turn_id(char c) { return strchr(turn, c) - turn; }
int dr[] = { -1,0,1,0 }; int dc[] = { 0,1,0,-1 };/*四个去向造成的行列变换*/
struct Node {
/*结点应拥有行和列以及进来的方向这三个性质，可行性交给数组*/
int r;
int c;
int dir;
Node(int rr = 0, int cc = 0, int dir_id = 0) :r(rr), c(cc), dir(dir_id) {}
};
Node walk(const Node& p, int turn) {
/*以现有结点得出接下来的结点，用const*/
int dir = p.dir;
/*左右转之间的规律*/
if (turn == 1)dir = (dir + 3) % 4;
if (turn == 2)dir = (dir + 1) % 4;
return Node(p.r + dr[dir], p.c + dc[dir], dir);
}
bool inside(int r, int c) { return r >= 1 && r <= 9 && c >= 1 && c <= 9; }/*是否越界合法性检测*/
int has_edge[maxn][maxn][4][3];/*可行性*/
int r0, c0, r1, c1, r2, c2;/*定义三个特征量 起点 第一个行驶点 终点*/
int dir_f;
bool read_case() {
char s1[99], s2[99];
/*循环头的语句从左至右按顺序执行--int point 1*/
if(scanf("%s %d %d %c %d %d", s1,&r0, &c0, &s2[0], &r2, &c2)!=6)return false;/*开始方向的作用是得出（r1，c1）*/
memset(has_edge, 0, sizeof(has_edge));
dir_f = dir_id(s2[0]);
r1 = r0 + dr[dir_f]; c1 = c0 + dc[dir_f];
int r = 0, c = 0;
while (scanf("%d", &r) == 1 && r != 0) {
/*单个特殊值阻断输入，需将该输入隔离开*/
scanf("%d", &c);
while (scanf("%s", s2) == 1 && s2[0] != '*')
for (int i = strlen(s2) - 1; i > 0; i--)
has_edge[r][c][dir_id(s2[0])][turn_id(s2[i])] = 1;/*合法性图建立*/
}
cout << s1 << endl;
return true;
}
/*BFS部分*/
/*游戏开始--从起点开始，直到终点，尽量不重复，面对三个方向遍历--BFS*/
Node q[maxn][maxn][4];/*存储结点*/
int d[maxn][maxn][4];/*观察是否已经遍历过,加入方向的原因--同向同格必重复*/
void print_ans(Node u)
{/*寻找到终点时需要输出*/
vector<Node>op;
op.push_back(u);
Node v = q[u.r][u.c][u.dir];
for (;;) {
op.push_back(v);
if (d[v.r][v.c][v.dir] == 0)break;
v = q[v.r][v.c][v.dir];
}
op.push_back(Node(r0, c0, dir_f));
int cnt = 0;
printf(" ");
for (int i = op.size() - 1; i >= 0; i--) {
printf("(%d,%d)", op[i].r, op[i].c);
cnt++;
if (cnt % 10 != 0 && i != 0)printf(" ");
if (cnt % 10 == 0)printf("\n ");
if (i == 0)cout << endl;
}
}
void solve() {
memset(d, -1, sizeof(d));
Node u(r1, c1, dir_f);
d[u.r][u.c][u.dir] = 0;
queue<Node>qu;
qu.push(u);
while (!qu.empty()) {
Node w = qu.front(); qu.pop();
if (w.r == r2 && w.c == c2) { print_ans(w); return; }
for (int i = 0; i < 3; i++) {
if (has_edge[w.r][w.c][w.dir][i]) {
Node v = walk(w, i);
if (d[v.r][v.c][v.dir] < 0 && inside(v.r, v.c))
{
qu.push(v);
q[v.r][v.c][v.dir] = w;/*存树*/
d[v.r][v.c][v.dir] = d[w.r][w.c][w.dir] + 1;/*寻找路径至出发点!!！*/
}
}
}
}
printf(" No Solution Possible\n");/*缩进两格*/
}
int main() {
while (read_case()) {
solve();
}
return 0;
}
思路和紫书上的基本相同，但是time limit exceeded
题目贴一下
time limit exceeded
超过时间限制
分析1、没有循环终止条件。
例：while(scanf()!=EOF)
分析2、函数调用超时、程序算法不够优化
看了你的代码，个人偏向第一种