matrix_path

Jan 6th, 2022
635
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Solution {
2. public:
3.     int m;
4.     int n;
5.     vector<vector<char>> board;
6.     vector<vector<bool>> visited;
7.     bool dfs(int curx, int cury, string &word, int curp, vector<vector<bool>> &visited){
8.         if(curp == word.size()) return true;
9.         if(curx < 0 || cury < 0 || curx >= m || cury >= n) return false;
10.         if(visited[curx][cury] || board[curx][cury] != word[curp]) return false;
11.         visited[curx][cury] = true;
12.         return  dfs(curx, cury + 1, word, curp + 1, visited) ||
13.                 dfs(curx, cury - 1, word, curp + 1, visited) ||
14.                 dfs(curx + 1, cury, word, curp + 1, visited) ||
15.                 dfs(curx - 1, cury, word, curp + 1, visited);
16.     }
17.     bool exist(vector<vector<char>>& board, string word) {
18.         this->m = board.size();
19.         this->n = board[0].size();
20.         this->board = board;
21.         for(int i = 0; i < m; i++){
22.             for(int j = 0; j < n; j++){
23.                 visited.resize(m, vector<bool>(n, false));
24.                 if(dfs(i, j, word, 0, visited)) return true;
25.             }
26.         }
27.         return false;
28.     }
29. };