某机试题:Word Maze(单词迷宫)

描述:

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;
}

 

  1. rin说道:
    Google Chrome Windows 10
    dfs~~
  2. 石櫻燈籠说道:
    Google Chrome Windows 7
    ……如上图,木有看到上图
    1. 一树小草说道:
      Firefox Android 6.0.1
      华为自己的图挂了,不过没图倒是也不影响题意理解。

回复 rin 取消回复

电子邮件地址不会被公开。必填项已用 * 标注