Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- class Solution {
- static class Node
- {
- public Node(int x, int y)
- {
- this.x = x;
- this.y = y;
- }
- int x;
- int y;
- }
- public int maxAreaOfIsland(int[][] grid) {
- int maxRows = grid.length;
- int maxCols = grid[0].length;
- int maxIslandArea = 0;
- // Used to check if a 1 has been visited when performing BFS or DFS
- boolean[][] isNodeCheckedGrid = new boolean[maxRows][maxCols];
- // Check for the largest island by iterating through the grid
- for (int i = 0; i < maxRows; ++i)
- {
- for (int j = 0; j < maxCols; ++j)
- {
- // When we encounter a 1 and that 1 is not yet checked, then perform BFS at that node
- if (grid[i][j] == 1 && isNodeCheckedGrid[i][j] == false)
- {
- int islandArea = countIslandBFS(new Node(i, j), isNodeCheckedGrid, grid);
- if (islandArea > maxIslandArea)
- {
- maxIslandArea = islandArea;
- }
- }
- }
- }
- return maxIslandArea;
- }
- // Perform an iterative BFS to count connected 1s
- public static int countIslandBFS(Node startNode, boolean[][] isCheckedGrid, int[][] grid)
- {
- int islandArea = 0;
- // Our priorityQ that stores our visited nodes
- Deque<Node> bfsQueue = new ArrayDeque<Node>();
- bfsQueue.add(startNode);
- while (bfsQueue.size() != 0)
- {
- islandArea++;
- Node currNode = bfsQueue.pop();
- Node leftNode = new Node(currNode.x - 1, currNode.y);
- Node rightNode = new Node(currNode.x + 1, currNode.y);
- Node topNode = new Node(currNode.x, currNode.y + 1);
- Node downNode = new Node(currNode.x, currNode.y - 1);
- // Check left
- if (isWithinGrid(leftNode, isCheckedGrid) && grid[leftNode.x][leftNode.y] == 1)
- {
- bfsQueue.add(leftNode);
- }
- // Check right
- if (isWithinGrid(rightNode, isCheckedGrid) && grid[rightNode.x][rightNode.y] == 1)
- {
- bfsQueue.add(rightNode);
- }
- // Check top
- if (isWithinGrid(topNode, isCheckedGrid) && grid[topNode.x][topNode.y] == 1)
- {
- bfsQueue.add(topNode);
- }
- // Check down
- if (isWithinGrid(downNode, isCheckedGrid) && grid[downNode.x][downNode.y] == 1)
- {
- bfsQueue.add(downNode);
- }
- }
- return islandArea;
- }
- // Simple boolean check to see if a node is within our grid
- public static boolean isWithinGrid(Node node, boolean[][] grid)
- {
- if (node.x >= 0 && node.x < grid.length && node.y >= 0 && node.y < grid[0].length)
- {
- if (grid[node.x][node.y] == false)
- {
- grid[node.x][node.y] = true;
- return true;
- }
- }
- return false;
- }
- }
Add Comment
Please, Sign In to add comment