816 - Abbott‘s Revenge （UVA）

本文主要是介绍816 - Abbott‘s Revenge （UVA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接如下：

Online Judge

刘汝佳大佬的代码如下：

uva 816（经典bfs例子）-CSDN博客

有点抽象，但很简洁。

我自己的代码比较臃肿，又臭又长....而且改了很久才AC。暂时没力气写刘汝佳的版本了...我的代码如下：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
// #define debugstruct loc{int r, c, prev;char direction;loc(int _r, int _c, int _prev, char _d): r(_r), c(_c), prev(_prev), direction(_d){}
};
std::string name, direction, str;
int startR, startC, exitR, exitC, r, c, pivot, nextR, nextC;
std::vector<std::string> dir[10][10];
std::vector<std::string> empty;
std::vector<int> path;
std::vector<loc> vec;
bool flag, newloc;
char d, newd;bool isValid(int u, int v){if (u < 1 || u > 9 || v < 1 || v > 9){return false;}return true;
}void printPath(){int p = vec.size() - 1;do {path.push_back(p);p = vec[p].prev;} while (p >= 0);reverse(path.begin(), path.end());for (int i = 0; i < path.size(); ++i){printf(" (%d,%d)", vec[path[i]].r, vec[path[i]].c);if ((i + 1) % 10 == 0){printf("%s", i == path.size() - 1 ? "\n" : "\n ");} else if (i == path.size() - 1){printf("\n");}}
}int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifwhile (std::cin >> name && name != "END"){printf("%s\n ", name.c_str());for (int i = 1; i <= 9; ++i){for (int j = 1; j <= 9; ++j){dir[i][j] = empty;}}vec.clear();path.clear();flag = false;std::cin >> startR >> startC >> direction >> exitR >> exitC;while (std::cin >> r && r){std::cin >> c;while (std::cin >> str && str != "*"){dir[r][c].push_back(str);}}r = startR;c = startC;if (direction == "E"){c++;} else if (direction == "W"){c--;} else if (direction == "S"){r++;} else if (direction == "N"){r--;}if (r == exitR && c == exitC){printf(" (%d,%d) (%d,%d)\n", startR, startC, r, c);continue;}vec.push_back(loc(startR, startC, -1, ' '));vec.push_back(loc(r, c, 0, direction[0]));pivot = 1;while (pivot < vec.size()){r = vec[pivot].r;c = vec[pivot].c;d = vec[pivot].direction;for (int i = 0; i < dir[r][c].size(); ++i){if (dir[r][c][i][0] == d){for (int j = 1; j < dir[r][c][i].size(); ++j){nextR = r;nextC = c;if (dir[r][c][i][j] == 'L'){if (d == 'E'){newd = 'N';} else if (d == 'N'){newd = 'W';} else if (d == 'S'){newd = 'E';} else if (d == 'W'){newd = 'S';}} else if (dir[r][c][i][j] == 'R'){if (d == 'E'){newd = 'S';} else if (d == 'N'){newd = 'E';} else if (d == 'W'){newd = 'N';} else if (d == 'S'){newd = 'W';}} else if (dir[r][c][i][j] == 'F'){newd = d;}if (newd == 'E'){nextC++;} else if (newd == 'W'){nextC--;} else if (newd == 'S'){nextR++;} else if (newd == 'N'){nextR--;}newloc = true;for (int k = 0; k < vec.size(); ++k){if (vec[k].r == nextR && vec[k].c == nextC && vec[k].direction == newd){newloc = false;break;}}if (newloc && isValid(nextR, nextC)){vec.push_back(loc(nextR, nextC, pivot, newd));if (nextR == exitR && nextC == exitC){printPath();i = dir[r][c].size();pivot = vec.size();flag = true;break;}}}}}pivot++;}if (!flag){printf(" No Solution Possible\n");}}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}

这篇关于816 - Abbott‘s Revenge （UVA）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---