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