ClosestG { public static int[][] minSteps(char[][] board) { int rows = board.length; int columns = board[0].length; int[][] closest = new int[rows][columns]; Set<Integer> visited = new HashSet<>(); Set<Integer> lastVisited = new HashSet<>(); for (int row = 0; row < rows; row++) { for (int column = 0; column < columns; column++) { char c = board[row][column]; if ('G' == c) { closest[row][column] = 0; visited.add(row * columns + column); lastVisited.add(row * columns + column); } else { if ('W' == c) { visited.add(row * columns + column); } closest[row][column] = Integer.MAX_VALUE; } } } int n = visited.size(); if (n == 0) { return closest; } int[][] moves = new int[][]{ {-1, 0}, {0, -1}, {1, 0}, {0, 1} }; int step = 0; do { n = visited.size(); Set<Integer> neighbors = new HashSet<>(); for (int pos : lastVisited) { int row = pos / columns; int column = pos % columns; for (int[] move: moves) { int nextR = row + move[0]; int nextC = column + move[1]; if (nextR >= 0 && nextR < rows && nextC >= 0 && nextC < columns) { int nextPos = nextR * columns + nextC; if(!visited.contains(nextPos)) { neighbors.add(nextPos); } } } } step++; for (int neighbor: neighbors) { int row = neighbor / columns; int column = neighbor % columns; closest[row][column] = step; } lastVisited = neighbors; visited.addAll(lastVisited); } while (n < visited.size()); return closest; }  static int[][] minSteps(char[][] board);  }
@Test(dataProvider = "closestGMatrix") public void testClosestG(char[][] matrix, int[][] expected) { assertEquals(ClosestG.minSteps(matrix), expected); }