Monday, August 8, 2016

Google – Maximum Perimeter of Same Color

Google – Maximum Perimeter of Same Color

[Solution]
dfs，每到一个cell, 有4条边，check上下左右四个方向，如果哪个方向上的cell颜色相同，就减一条边。

`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;`
`  ``}`
`}`