leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0079.cpp (1159B)

      1 class Solution {
      2     typedef vector<vector<char>> Matrix;
      3     typedef vector<vector<bool>> Marked;
      4     const vector<pair<int, int>> offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
      5 
      6     int n, m;
      7     int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
      8 
      9     string word;
     10     bool dfs(const Matrix &mat, Marked &mark, int a, int b, int got) {
     11         if (got == word.size()) return true;
     12 
     13         mark[a][b] = true;
     14         for (auto [oa, ob] : offsets) {
     15             int x = a + oa, y = b + ob;
     16             if (!valid(x, y) || mark[x][y] || mat[x][y] != word[got]) continue;
     17             if (dfs(mat, mark, x, y, got + 1)) return true;
     18         }
     19         mark[a][b] = false;
     20 
     21         return false;
     22     }
     23 
     24   public:
     25     bool exist(const Matrix &board, string word) {
     26         n = board.size(), m = board[0].size();
     27         this->word = word;
     28 
     29         Marked visited(n, vector<bool>(m, false));
     30 
     31         for (int i = 0; i < n; i++) {
     32             for (int j = 0; j < m; j++) {
     33                 if (board[i][j] != word[0]) continue;
     34                 if (dfs(board, visited, i, j, 1)) return true;
     35             }
     36         }
     37 
     38         return false;
     39     }
     40 };