use std::collections::HashMap;
impl Solution {
fn compute_area(x: i32, y: i32, color: i32, grid: &mut Vec<Vec<i32>>) -> i32 {
let (m, n) = (grid.len(), grid[0].len());
if x < 0 || x >= m as i32 || y < 0 || y >= n as i32 || grid[x as usize][y as usize] != 1 {
return 0;
}
grid[x as usize][y as usize] = color;
let ret = 1 + Self::compute_area(x + 1, y, color, grid) +
Self::compute_area(x - 1, y, color, grid) +
Self::compute_area(x, y + 1, color, grid) +
Self::compute_area(x, y - 1, color, grid);
return ret;
}
fn get_color(x: i32, y: i32, grid: &Vec<Vec<i32>>) -> i32 {
let (m, n) = (grid.len(), grid[0].len());
if x < 0 || y < 0 || x >= m as i32 || y >= n as i32 {
return 0;
}
return grid[x as usize][y as usize];
}
pub fn largest_island(grid: Vec<Vec<i32>>) -> i32 {
println!("{}", grid.len());
let (m, n, mut ans) = (grid.len(), grid[0].len(), 0);
let mut g = grid.clone();
let mut map = HashMap::new();
map.insert(0, 0);
let mut color = 0;
for i in 0..m {
for j in 0..n {
if grid[i][j] == 1 {
color += 1;
let val = Self::compute_area(i as i32, j as i32,
color, &mut g);
map.insert(color, val);
ans = std::cmp::max(ans, val);
}
}
}
for i in 0..m {
for j in 0..n {
if grid[i][j] == 0 {
let mut area = 1;
let keys = [Self::get_color(i as i32, j as i32 - 1, &g),
Self::get_color(i as i32, j as i32 + 1, &g),
Self::get_color(i as i32 - 1, j as i32, &g),
Self::get_color(i as i32 + 1, j as i32, &g)];
for key in &keys {
area += *map.get(&key).unwrap();
ans = std::cmp::max(ans, area);
}
}
}
}
return ans;
}
}
|