UVA 816 (写的全是bug，手动呲牙）

bfs失败。mark

我他妈服了自己/cy
注释

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N = 15;
int r1, c1, dir;
int end_r, end_c;
char title[1000];
const char* dirs = "NESW";
const char* turns = "FLR";
const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 };
int dir_id(char c) { return strchr(dirs, c) - dirs; }
int turn_id(char c) { return strchr(turns, c) - turns; }
struct Node {
int r, c, dir;
Node() {};
//Node (Node&t) :r(t.r), c(t.c), dir(t.dir) {};
};
int d[N][N][4];
Node P[N][N][4];
bool has_edge[N][N][4][3];
int input();
Node walk(Node &u, int turn);
void slove();
void print_path(Node u);
int main() {
while (input()) {
slove();
//cout << "input sucessfullyn";
}
}
int input() {
scanf("%s", title);
if (strcmp(title, "END") == 0)
return 0;
printf("%sn", title);
int r, c;char Dir;char s[1000];
cin >> r >> c;scanf(" %c", &Dir);cin >> end_r >> end_c;
dir = dir_id(Dir);
r1 = r + dr[dir_id(Dir)];
c1 = c + dc[dir_id(Dir)];
while (cin >> r && r) {
cin >> c;
while (scanf("%s", s)) {
if (strcmp(s, "*") != 0) {
for (int i = 1;s[i] != '';i++)
has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = true;
}
else
break;
}
}
return 1;
}
Node walk(Node &u, int turn) {
//u的dir给你改了
/cy
Node p;
if (turn == 1) u.dir = (u.dir + 3) % 4;
if (turn == 2) u.dir = (u.dir + 1) % 4;
p.c = u.c + dc[u.dir];
p.r = u.r + dr[u.dir];
p.dir = u.dir;
return p;
}
void slove() {
memset(d, -1, sizeof(d));
queue<Node>p;
Node u;u.c = c1;u.r = r1;u.dir = dir;
p.push(u);
d[r1][c1][dir] = 0;
while (!p.empty()) {
Node t = p.front();
p.pop();
if (t.r = end_r && t.c == end_c) { //你这个赋值是什么骚操作/cy ,以后全部倒过来写算了
print_path(t);
return;
}
for (int i = 0;i < 3;i++) {
Node r;
r = walk(t, i);
if (has_edge[t.r][t.c][t.dir][i] && d[r.r][r.c][r.dir] == 0) {
p.push(r);
P[r.r][r.c][r.dir] = t;
//这里忘记了更新d[][][]
}
}
}
cout << "No Solutions" << endl;
}
void print_path(Node u) {
vector<Node>q;
q.push_back(u);
for (;;) {
if (d[u.r][u.c][u.dir] == 0)
break;
u = P[u.r][u.c][u.dir];
q.push_back(u);
}
//没把起点也给搞进去
for (int i = q.size() - 1;i >= 0;i--) {
printf("(%d,%d) ", q[i].r, q[i].c);
}//输出格式到时候改一改就好了
}

改了之后

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int N = 15;
int r1, c1, dir;
int r0, c0;
int end_r, end_c;
char title[1000];
const char* dirs = "NESW";
const char* turns = "FLR";
const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 };
int dir_id(char c) { return strchr(dirs, c) - dirs; }
int turn_id(char c) { return strchr(turns, c) - turns; }
struct Node {
int r, c, dir;
Node() {};
Node(int r, int c, int dir) :r(r), c(c), dir(dir) {};
//Node (Node&t) :r(t.r), c(t.c), dir(t.dir) {};
};
int d[N][N][4];
Node P[N][N][4];
bool has_edge[N][N][4][3];
int input();
Node walk(Node u, int turn);
void slove();
void print_path(Node u);
int main() {
while (input()) {
slove();
//cout << "input sucessfullyn";
}
}
int input() {
scanf("%s", title);
if (strcmp(title, "END") == 0)
return 0;
int r, c;char Dir;char s[1000];
cin >> r >> c;scanf(" %c", &Dir);cin >> end_r >> end_c;
dir = dir_id(Dir);
r1 = r + dr[dir_id(Dir)];
c1 = c + dc[dir_id(Dir)];
r0 = r;
c0 = c;
while (cin >> r && r) {
cin >> c;
while (scanf("%s", s)) {
if (strcmp(s, "*") != 0) {
for (int i = 1;s[i] != '';i++)
has_edge[r][c][dir_id(s[0])][turn_id(s[i])] = true;
}
else
break;
}
}
return 1;
}
Node walk(Node u, int turn) {
Node p;
if (turn == 1) u.dir = (u.dir + 3) % 4;
if (turn == 2) u.dir = (u.dir + 1) % 4;
p.c = u.c + dc[u.dir];
p.r = u.r + dr[u.dir];
p.dir = u.dir;
return p;
}
void slove() {
printf("%sn", title);
memset(d, -1, sizeof(d));
queue<Node>p;
Node u;u.c = c1;u.r = r1;u.dir = dir;
p.push(u);
d[r1][c1][dir] = 0;
while (!p.empty()) {
Node t = p.front();
p.pop();
if (t.r == end_r && t.c == end_c) {
print_path(t);
return;
}
for (int i = 0;i < 3;i++) {
Node r;
r = walk(t, i);
if (has_edge[t.r][t.c][t.dir][i] && d[r.r][r.c][r.dir] < 0) {
p.push(r);
P[r.r][r.c][r.dir] = t;
d[r.r][r.c][r.dir] = d[t.r][t.c][t.dir] + 1;
}
}
}
cout << "
No Solution Possible" << endl;
}
void print_path(Node u) {
vector<Node>q;
q.push_back(u);
for (;;) {
if (d[u.r][u.c][u.dir] == 0)
break;
u = P[u.r][u.c][u.dir];
q.push_back(u);
}
q.push_back(Node(r0, c0, dir));
int cnt = 0;
for (int i = q.size() - 1;i >= 0;i--) {
if (cnt % 10 == 0)
putchar(' ');
printf(" (%d,%d)", q[i].r, q[i].c);
if (++cnt % 10 == 0)
putchar('n');
}
if (q.size() % 10 != 0) printf("n");
}

/cy 样例过了但是WA了 /cy

先放弃了，我真实弟弟。

结构体的构造函数和复制函数还没有搞太明白。

最后

以上就是聪慧唇彩为你收集整理的UVA 816 (写的全是bug，手动呲牙）的全部内容，希望文章能够帮你解决UVA 816 (写的全是bug，手动呲牙）所遇到的程序开发问题。

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