private boolean dfs(int r, int c, String w, int idx, boolean[][] used, char[][] board) {
	        used[r][c] = true; // modify
	        char ch = w.charAt(idx);
	        if (ch == board[r][c]) {
	            if (idx == w.length()-1)
	                return true;
	            for (int[] dir : dirs) {
	                int r1 = r + dir[0], c1 = c + dir[1];
	                if (r1 >= 0 && r1 < board.length && c1 >= 0 && c1 < board[0].length && !used[r1][c1]) {
	                    if (dfs(r1, c1, w, idx+1, used, board))
	                        return true;
	                }
	            }
	        }
	        used[r][c] = false; // restore
	        
	        return false;
	    }