Advertisement
ambition-xx

matrix_path

Jan 6th, 2022
635
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  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. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement