leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0079.cpp (1159B)

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