[itint5] 36 - 单词游戏 - 阿牧遥 - 博客园

[itint5]单词游戏 - 阿牧遥 - 博客园
http://www.itint5.com/oj/#36
https://github.com/AnnieKim/ITint5/blob/master/036_%E5%8D%95%E8%AF%8D%E6%B8%B8%E6%88%8F.cpp
一个n*m的字母网格grid，格子中的字母属于26个大写字母。
 选择某个格子作为起始点，每一步可以移动到上下左右相邻的格子中，这样遍历经过的字母组成了单词（每个格子只能访问一次）。
 判断是否能够在网格中找到给定的单词pattern。
 样例：
 n=3,m=4
 Grid:
 PACD
 BGHI
 MNDC
 对于pattern = "DCHGB"，返回true。
 对于pattern = "PBGNDC", 返回true。
 对于pattern = "CIDCB"，返回false。
 Solution: 和LeetCode中Word Search一题重复。DFS。
*/

bool existsRe(vector<vector<char> > &grid, string &pattern,
              int start, int i, int j, vector<vector<bool> > &visited) {
    int N = grid.size(), M = grid[0].size();
    if (start == pattern.size()) return true;
    if (i < 0 || i >= N || j < 0 || j >= M) return false;
    if (grid[i][j] != pattern[start] || visited[i][j]) return false;
   
    visited[i][j] = true;
    if (existsRe(grid, pattern, start + 1, i-1, j, visited)) return true;
    if (existsRe(grid, pattern, start + 1, i+1, j, visited)) return true;
    if (existsRe(grid, pattern, start + 1, i, j-1, visited)) return true;
    if (existsRe(grid, pattern, start + 1, i, j+1, visited)) return true;
    visited[i][j] = false;
    return false;
}

bool exists(vector<vector<char> > &grid, string pattern) {
    if (grid.empty()) return false;
    if (pattern.empty()) return true;
    int N = grid.size(), M = grid[0].size();
    vector<vector<bool> > visited(N, vector<bool>(M, false));
    for (int i = 0; i < N; ++i)

        for (int j = 0; j < M; ++j)
            if (existsRe(grid, pattern, 0, i, j, visited))
                return true;
    return false;
}
https://github.com/zdzapple/itint5/blob/master/%E5%8D%95%E8%AF%8D%E6%B8%B8%E6%88%8F.cpp
bool dfs(const vector<vector<char> > &grid,
vector<vector<bool> > &isVisited,
const string &pattern,
int currentIndex,
int row, int col)
{
isVisited[row][col] = true;
int n = grid.size();
int m = grid[0].size();
if (currentIndex == pattern.size() - 1) {
isVisited[row][col] = false;
return true;
}
bool success = false;
if (row < n-1 && grid[row+1][col] == pattern[currentIndex + 1] && !isVisited[row+1][col]) {
if (dfs(grid, isVisited, pattern, currentIndex + 1, row + 1, col)) {
success = true;
}
}
if (!success && row > 0 && grid[row-1][col] == pattern[currentIndex + 1] && !isVisited[row-1][col]) {
if (dfs(grid, isVisited, pattern, currentIndex + 1, row - 1, col))
success = true;
}
if (!success && col < m-1 && grid[row][col+1] == pattern[currentIndex + 1] && !isVisited[row][col+1]) {
if (dfs(grid, isVisited, pattern, currentIndex + 1, row, col + 1))
success = true;
}
if (!success && col > 0 && grid[row][col-1] == pattern[currentIndex + 1] && !isVisited[row][col-1]) {
if (dfs(grid, isVisited, pattern, currentIndex + 1, row, col - 1))
success = true;
}

isVisited[row][col] = false;
return success;
}

bool exists(vector<vector<char> > &grid, string pattern)
{
if (grid.empty())
return false;
if (pattern.empty())
return true;
int n = grid.size();
int m = grid[0].size();

vector<vector<bool> > isVisited(n, vector<bool>(m, false));
for (int i = 0; i < n; ++ i)
{
for (int j = 0; j < m; ++ j)
{
if (pattern[0] == grid[i][j]) {
if (dfs(grid, isVisited, pattern, 0, i, j))
return true;
}
}
}
return false;
}
此题在数据大些，而且全是A的情况下会超时（因为要匹配到很后面才false）。通过利用数组本身作为visited标示，而且使用string引用，得意通过

bool find(vector<vector<char> > &grid, string &pattern, int i, int j, int k) {

    if (k == pattern.length()) return true;

    int m = grid.size();

    int n = grid[0].size();

    if (i < 0 || i >= m || j < 0 || j >= n) return false;

    if (pattern[k] == grid[i][j] && grid[i][j] != '#') {

        char c = grid[i][j];

        grid[i][j] = '#';

        if (find(grid, pattern, i-1, j, k+1) ||

            find(grid, pattern, i+1, j, k+1) ||

            find(grid, pattern, i, j-1, k+1) ||

            find(grid, pattern, i, j+1, k+1)) {

            grid[i][j] = c;

            return true;

        } else {

            grid[i][j] = c;

            return false;

        }

    } else {

        return false;

    }

}

 

bool exists(vector<vector<char> > &grid, string pattern) {

    int m = grid.size();

    if (m == 0) return false;

    int n = grid[0].size();

    if (n == 0) return false;

    for (int i = 0; i < m; i++) {

        for (int j = 0; j < n; j++) {

            if (find(grid, pattern, i, j, 0)) return true;

        }

    }

    return false;

}

Read full article from [itint5]单词游戏 - 阿牧遥 - 博客园