leetcode

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 };