Leetcode 79 - Word Search（dfs）

2019-11-08 03:04:12

字体：大中小

来源：转载

供稿：网友

题意

求一个字符串是否能从矩形内某一点出发，沿上下左右走得到。

思路

dfs。

算法1

用use[i][j]记录位置[i, j]是否被访问过，dfs就好。

算法2

我们访问一个位置的时候，把它记为’#’，访问完还原即可。

代码

//algorithm 1const int maxn = 205;int use[maxn][maxn];class Solution {PRivate: int m, n; int dx[4], dy[4]; string Word;public: Solution() { dx[0] = -1, dx[1] = 1, dx[2] = 0, dx[3] = 0; dy[0] = 0, dy[1] = 0, dy[2] = -1, dy[3] = 1; } bool dfs(int x, int y, int pos, vector<vector<char>>& a) { if (pos == word.size() - 1) return word[pos] == a[x][y]; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && !use[nx][ny] && a[nx][ny] == word[pos + 1]) { use[nx][ny] = 1; if (dfs(nx, ny, pos + 1, a)) return true; use[nx][ny] = 0; } } return false; } bool exist(vector<vector<char>>& board, string word) { m = board.size(); if (m) { n = board[0].size(); this->word = word; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == word[0]) { memset(use, 0, sizeof(use)); use[i][j] = 1; if (dfs(i, j, 0, board)) return true; } } } } return false; }};//algorithm 2class Solution {private: int m, n; int dx[4], dy[4]; string word;public: Solution() { dx[0] = -1, dx[1] = 1, dx[2] = 0, dx[3] = 0; dy[0] = 0, dy[1] = 0, dy[2] = -1, dy[3] = 1; } bool dfs(int x, int y, int pos, vector<vector<char>>& a) { if (pos == word.size() - 1) return word[pos] == a[x][y]; int t = a[x][y]; a[x][y] = '#'; for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && a[nx][ny] == word[pos + 1]) { if (dfs(nx, ny, pos + 1, a)) return true; } } a[x][y] = t; return false; } bool exist(vector<vector<char>>& board, string word) { m = board.size(); if (m) { n = board[0].size(); this->word = word; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == word[0]) { if (dfs(i, j, 0, board)) return true; } } } } return false; }};

上一篇：[BZOJ1492][NOI2007][CDQ分治][斜率优化][DP]货币兑换Cash

下一篇：[BZOJ3963][WF2011][CDQ分治][斜率优化][DP]MachineWorks

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注