AC, but is there a more concise way to check neighbors of a 2D array?


  • 1
    A
    public class Solution {
    private int width;
    private int height;
    private char[][] board;
    private String word;
    public boolean exist(char[][] brd, String wrd) {
    	// Store parameters that won't change
    	if((height = brd.length) == 0 ) return false;
    	if((width  = brd[0].length)==0) return false;
    	if(wrd.length()==0) return true;
    	board = brd; word = wrd;
    	// Locate the root by looking 
    	// for the 1st character
    	// in the board
    	for (int y = 0; y < height; y ++) {
    		for (int x = 0; x < width; x ++) {
    			if (board[y][x] == word.charAt(0))
    				if (dfs(y,x,1,new boolean[height][width]) == true) return true;
    		}
    	}
    	return false;
    }
    
    // Use DFS other than BFS, because the "visited" map is commonly used
    public boolean dfs(int cy, int cx, int idx, boolean[][] visited) {
    	// If no more characters, the search is completed successfully
    	if (idx == word.length()) return true;
    	boolean found = false;
    	visited[cy][cx] = true;
        // The part of code I do not feel like writing evertime ---------------------------->
    	// Check left neighbor if current not on the left boundary
    	// If word[idx] is found, proceed by a recursive call
    	if (cx > 0) {
    		if (visited[cy][cx-1] == false && board[cy][cx-1] == word.charAt(idx))
    			found = dfs(cy, cx-1, idx + 1, visited);
    	}
    	// Right neighbor
    	if (cx < width - 1 && found == false) {
    		if (visited[cy][cx+1] == false && board[cy][cx+1] == word.charAt(idx))
    			found = dfs(cy, cx+1, idx + 1, visited);
    	}
    	// Up neighbor
    	if (cy > 0 && found == false) {
    		if (visited[cy-1][cx] == false && board[cy-1][cx] == word.charAt(idx))
    			found = dfs(cy-1, cx, idx + 1, visited);
    	}
    	// Down neighbor
    	if (cy < height - 1&& found == false) {
    		if (visited[cy+1][cx] == false && board[cy+1][cx] == word.charAt(idx))
    			found = dfs(cy+1, cx, idx + 1, visited);
    	}
    	// <--------------------------------------------------------------------------------------------
    	// Undo visited to current tile if search wasn't successful
    	if (found == false) {
    		visited[cy][cx] = false;
    	} return found;		
    }
     }
    

    Common to questions related to graph searching and 2D arrays, there are x and y coordinates and 4 corners ULFR to search, so I cannot write code as cool as

    for (Node n : (Iterable<Node>)neighbors) { //... }
    

    to check all of them.

    I tried mapping the 2D array to 1D as using

    int id = x + board_width * y;
    int x  = id % board_width;
    int y = id / board_width;
    

    but that also makes the code complex and slightly added constant computation cost.
    So is there any concise solution to code for graphs in 2D arrays?


  • 2
    M
     static final int[] deli = {0,0,1,-1} ;
     static final int[] delj = {1,-1,0,0} ;
    

    and then

    for(int m=0; m<4; m++){
                int ni = i+deli[m];
                int nj = j+delj[m];
                if(safe(board,ni,nj)){
                    ...
                    } 
                }
            }
    

    where safe() just checks bounds

    You can also add diagonal neighbours to del arrays


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.