描述: |
Word Maze 是一个网络小游戏,你需要找到以字母标注的食物,但要求以给定单词字母的顺序吃掉。如上图,假设给定单词 if,你必须先吃掉i然后才能吃掉f。 但现在你的任务可没有这么简单,你现在处于一个迷宫Maze(n×m的矩阵)当中,里面到处都是以字母标注的食物,但你只能 吃掉能连成给定单词W的食物。 如下图,指定W为“SOLO”,则在地图中红色标注了单词“SOLO”。 注意区分英文字母大小写,你只能上下左右行走。 |
运行时间限制: |
无限制 |
内存限制: |
无限制 |
输入: |
输入第一行包含两个整数n、m(0<n, m<21)分别表示n行m列的矩阵,第二行是长度不超过100的单词W,从第3行到底n+3行是只包含大小 写英文字母的长度为m的字符串。 |
输出: |
如果能在地图中连成给定的单词,则输出“YES”,否则输出“NO”。注意:每个字母只能用一次。 |
样例输入: |
5 5 SOLO CPUCY EKLQH CRSOL EKLQO PGRBC |
样例输出: |
YES |
不是很难,不过写起来蛮有意思的,所以稍稍贴个答案:
// Facility #include <utility> #include <iostream> #include <string> #include <functional> // Algorithm #include <algorithm> // Container #include <vector> class TempEraseChar { char tmp_; char& var_; public: TempEraseChar(char& var):var_(var) { tmp_ = var; var = '\0'; } ~TempEraseChar() { var_ = tmp_; } }; bool FindWorld(std::string& W, int n, std::vector<std::vector<char>>& maze, int i, int j) { if (n == W.size()) return true; if (maze[i][j] != W[n]) return false; TempEraseChar lock(maze[i][j]); return FindWorld(W, n + 1, maze, i + 1, j) || FindWorld(W, n + 1, maze, i - 1, j) || FindWorld(W, n + 1, maze, i, j + 1) || FindWorld(W, n + 1, maze, i, j - 1); } int main() { using namespace std; //N行,M列 int N, M; cin >> N >> M; string W; cin >> W; vector<vector<char>> maze(M + 2, vector<char>(N + 2, '\0')); for (int i = 0; i != N; i++) { for (int j = 0; j != M; j++) { cin >> maze[i + 1][j + 1]; } } for (int i = 1; i != N + 1; i++) { for (int j = 1; j != M + 1; j++) { if (FindWorld(W, 0, maze, i, j)) { cout << "YES"; return 0; } } } cout << "NO"; return 0; }