Word Search

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    int m = 0;
    int n = 0;

    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,1,-1};
    public boolean exist(char[][] board, String word) {
        // write your code here

        if (board == null || board.length == 0)
            return false;
        if (word == null || word.length() == 0)
            return true;

        m = board.length;
        n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean res = dfs(board, word, 0, i, j);
                if (res)
                    return true;

            }
        }

        return false;
    }

    public boolean dfs(char[][] board, String word, int index, int x, int y) {
        if (index == word.length()) {
            return true;
        }

        if (x < 0 || y < 0 || x >=m || y >= n || board[x][y] != word.charAt(index))
            return false;

        char temp = board[x][y];
        board[x][y] = '#';

        boolean res = false;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            res = res || dfs(board, word, index + 1, nx, ny);
        }
        board[x][y] = temp;
        return res;

    }
}

Number of islands

public class Solution {
    /**
     * @param grid a boolean 2D matrix
     * @return an integer
     */

    int m = 0;
    int n = 0;
    public int numIslands(boolean[][] grid) {
        // Write your code here
        if (grid == null || grid.length == 0)
            return 0;

        m = grid.length;
        n = grid[0].length;

        if (n == 0)
            return 0;

        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j]) {
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    public void dfs(boolean[][] grid, int x , int y) {
        if (x < 0 || y < 0 || x >= m || y >=n) {
            return;
        }

        if (grid[x][y]) {
            grid[x][y] = false;
            dfs(grid, x+1, y);
            dfs(grid, x-1, y);
            dfs(grid, x, y+1);
            dfs(grid, x, y-1);
        }
    }
}

Surrounded Regions

public class Solution {
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     * // bfs  http://blog.csdn.net/ljiabin/article/details/41345055
     */
    int m = 0;
    int n = 0;
    public void surroundedRegions(char[][] board) {
        // Write your code here

        if (board == null || board.length == 0)
            return;

        m = board.length;
        n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // act on all elements at the edges
                if (i == 0 || i == m-1 || j == 0 || j == n-1 ) {
                    if (board[i][j] == 'O')
                        dfs(board, i , j);
                }

            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                 if (board[i][j] == 'O')
                    board[i][j] = 'X';
                if (board[i][j] == '#')
                    board[i][j] = 'O';  
            }
        }

    }


    public void dfs (char[][] board, int x, int y) {

        board[x][y] = '#';

        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >=0 && nx <m && ny >= 0 && ny < n && board[nx][ny] == 'O')
                dfs(board, nx, ny);
        }

    }
}