Boggle Board

• Time : O(nm s 8 ^(maxlen(s))
• Space : O(nm)

#include <vector>
using namespace std;

bool dfs(vector<vector<char>>& board, int y, int x, string& w, vector<vector<bool>>& vis, int pos) {
	if(pos == w.length()) return true;
	if(0 <= y and y < board.size() and 0 <= x and x < board[0].size() and !vis[y][x]) {
		if(board[y][x] != w[pos]) return false;
		vis[y][x] = true;
		int dy[8]{-1,-1,-1,0,1,1,1,0}, dx[8]{-1,0,1,1,1,0,-1,-1};
		for(int i = 0; i < 8; i++) {
			int ny = y + dy[i], nx = x + dx[i];
			if(dfs(board,ny,nx,w,vis,pos+1)) {
				vis[y][x] = false;
				return true;
			}
		}
		vis[y][x] = false;
	}
	return false;
}

vector<string> boggleBoard(vector<vector<char>> board, vector<string> words) {
	int n = board.size(), m = board[0].size();
	vector<string> res;
	vector<vector<bool>> vis(n, vector<bool>(m));
  for(auto& w : words) {
		bool find = false;
		for(int i = 0; i < n and !find; i++) {
			for(int j = 0; j < m and !find; j++) {
				if(board[i][j] == w[0]) {
					find = dfs(board,i,j,w,vis,0);
				}
			}
		}
		if(find)
			res.push_back(w);
	}
  return res;
}