Google – Maximum Perimeter of Same Color

Google – Maximum Perimeter of Same Color
有一个grid，每个cell有一个颜色，然后现在给一个坐标(i, j)，求从这个点出发，沿着相同颜色走，找出一个颜色相同区域使得这个区域的周长最大。
[Solution]
dfs，每到一个cell, 有4条边，check上下左右四个方向，如果哪个方向上的cell颜色相同，就减一条边。
这题不用回溯，直接一路dfs到底。

class Solution {

  int result = 0;

  public int maxPerimeter(int[][] grid, int i, int j) {

    if (grid == null || grid.length == 0) {

      return 0;

    }

     

    dfs(grid, i, j, grid[i][j]);

    return result;

  }

   

  private void dfs(int[][] grid, int i, int j, int color) {

    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {

      return;

    }

    if (grid[i][j] != color) {

      return;

    }

     

    int curr = 4;

    grid[i][j] = -1;

    if (i - 1 >= 0 && (grid[i - 1][j] == color || grid[i - 1][j] == -1)) {

      curr--;

      dfs(grid, i - 1, j, color);

    }

    if (i + 1 < grid.length && (grid[i + 1][j] == color || grid[i + 1][j] == -1)) {

      curr--;

      dfs(grid, i + 1, j, color);

    }

    if (j - 1 >= 0 && (grid[i][j - 1] == color || grid[i][j - 1] == -1)) {

      curr--;

      dfs(grid, i, j - 1, color);

    }

    if (j + 1 < grid[0].length && (grid[i][j + 1] == color || grid[i][j + 1] == -1)) {

      curr--;

      dfs(grid, i, j + 1, color);

    }

     

    result += curr;

  }

}

Read full article from Google – Maximum Perimeter of Same Color