|
描述: |
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 |
不是很难，不过写起来蛮有意思的，所以稍稍贴个答案：
C++
// 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;
}
rin说道： 
Google Chrome 
Windows 10
石櫻燈籠说道： 
Windows 7
一树小草说道： 
Firefox 
Android 6.0.1