Problems

// 0 is empty, 1 is blocked, 2 is group1

package ai.jdd.prob;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Grid {

    private static int grid[][];

    public static void main(String[] args) {
        int rows = 5;
        int cols = 5;
        int numBlocks = (rows*cols)/2;

        for (int i = 0; i < 10; i++) {
            System.out.println("Is there more than one group? " + checkGrid(rows, cols, numBlocks));
        }
    }

    static boolean checkGrid(int rows, int cols, int numBlocks) {
        boolean oneGroup = false;
        grid = new int[rows][cols];
        for (int i=0; i<numBlocks; i++) {
            grid[(int)(Math.random()*rows)][(int)(Math.random()*cols)] = 1; //add in blocked cells
        }
        for (int[] row : grid)
            System.out.println(Arrays.toString(row));
        for (int x=0; x<rows; x++) { // iterate through grid
            for (int y=0; y<cols; y++) {
                if (grid[x][y] == 1) { // if this cell is blocked
                    if (oneGroup) {
                        return true; // found second group
                    }
                    oneGroup = true; // found first group
                    combineGroup(x,y);
                }
            }
        }
        return false; // 0 or 1 group found
    }

    private static void combineGroup(int x, int y) { // This method sets connected cells to 2
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, -1, 0, 1};
        Queue<Integer[]> q = new LinkedList<>();
        Integer point[] = {x,y};
        grid[x][y] = 2; // add it to group
        q.add(point); // queue of next cells to check

        while (!q.isEmpty()) {
            point = q.poll(); // get next cell to check

            for (int i = 0; i < 4; i++) { // check neighbors
                point[0] = dx[i]+x;
                point[1] = dy[i]+y;
                // check if in range and blocked
                if(point[0]>=0 && point[0]<grid.length && point[1]>=0 && point[1]<grid[0].length && grid[point[0]][point[1]] == 1) {
                    grid[point[0]][point[1]] = 2;
                    q.add(point);
                }
            }
        }
    }
}

package ai.jdd.prob;

import java.util.HashSet;
import java.util.Set;

public class Boggle {

    /*
    I chose DFS becuase I would have to store more state in memory if I had used BFS.

    List<String> ans is the list of answers, could make it a set remove duplicates

    solveBoggle's input is a matric of chars. For each char in the matrix, it will do a DFS for words

    searchWord's input is the board, coordinates, and the word so far.
    it adds the char to the word, and marks the coordinate in the board as 1

    it adds the word to the answer list if it is a word

    if the word is a prefix then it will run searchWord on its neighbors
     */

    private Set<String> ans = new HashSet<>(); //List of answers, right now there could be duplicate words

    Set<String> solveBoggle(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                searchWord(board, i, j, "");
            }
        }
        return ans;
    }

    private void searchWord(char[][] board, int row, int col, String word) {
        word += board[row][col];
        board[row][col] = '1';

        if(BoggleDict.isWord(word)) {
            ans.add(word);
        }

        if(BoggleDict.isPrefix(word)) {
            int[] dRow = {0,1,0,-1,-1,-1,1,1};
            int[] dCol = {-1,0,1,0,-1,1,-1,1};
            for (int i = 0; i < 8; i++) {
                int rowNeighb = dRow[i]+row;
                int colNeighb = dCol[i]+col;
                if (rowNeighb != -1 && rowNeighb != board.length && colNeighb != -1
                        && colNeighb != board[1].length && board[rowNeighb][colNeighb] != '1'){
                    searchWord(board, rowNeighb, colNeighb, word);
                }
            }
        }
    }

}