-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
94 lines (91 loc) · 3.23 KB
/
Program.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//思路与LeetCode 200相同,但在深度优先遍历时需额外记录每个岛屿的area。
//在主方法中每次遍历完一个岛屿就更新res。
using System;
using System.Collections.Generic;
using System.Threading;
namespace MaxAreaOfIsland
{
class Program
{
static void Main(string[] args)
{
int[][] grid = new int[4][];
grid[0] = new int[5] { 1, 1, 0, 0, 0 };
grid[1] = new int[5] { 1, 1, 0, 0, 0 };
grid[2] = new int[5] { 0, 0, 0, 1, 1 };
grid[3] = new int[5] { 0, 0, 0, 1, 1 };
Console.WriteLine(MaxAreaOfIsland(grid));
}
static int MaxAreaOfIsland_DFS(int[][] grid)
{
int res = 0;
int area = 0;
int[][] mark = new int[grid.Length][];
for (int i = 0; i < mark.Length; i++)
mark[i] = new int[grid[0].Length];
for (int i = 0; i < grid.Length; i++)
{
for (int j = 0; j < grid[0].Length; j++)
{
if (mark[i][j] == 0 && grid[i][j] == 1)
res = Math.Max(res, DFS(grid, mark, i, j, area));
}
}
return res;
}
static int DFS(int[][] grid, int[][] mark, int x, int y, int area)
{
area++;
mark[x][y] = 1;
int[] dx = { -1, 1, 0, 0 };
int[] dy = { 0, 0, -1, 1 };
for (int i = 0; i < 4; i++)
{
int newX = dx[i] + x;
int newY = dy[i] + y;
if (newX < 0 || newX >= grid.Length || newY < 0 || newY >= grid[0].Length)
continue;
if (mark[newX][newY] == 0 && grid[newX][newY] == 1)
area = Math.Max(area, DFS(grid, mark, newX, newY, area));
}
return area;
}
static int MaxAreaOfIsland(int[][] grid)
{
if (grid.Length == 0 || grid[0].Length == 0) return 0;
var mark = new int[grid.Length][];
for (int i = 0; i < grid.Length; i++)
mark[i] = new int[grid[0].Length];
var res = 0;
for (int x = 0; x < grid.Length; x++)
{
for (int y = 0; y < grid[0].Length; y++)
{
if (mark[x][y] == 0 && grid[x][y] == 1)
{
var area = 0;
GetArea(grid, mark, x, y, ref area);
res = Math.Max(res, area);
}
}
}
return res;
}
static void GetArea(int[][] grid, int[][] mark, int x, int y, ref int area)
{
mark[x][y] = 1;
area++;
int[] dx = { -1, 1, 0, 0 };
int[] dy = { 0, 0, -1, 1 };
for (int i = 0; i < 4; i++)
{
int newX = dx[i] + x;
int newY = dy[i] + y;
if (newX < 0 || newX >= grid.Length || newY < 0 || newY >= grid[0].Length)
continue;
if (grid[newX][newY] == 1 && mark[newX][newY] == 0)
GetArea(grid, mark, newX, newY, ref area);
}
}
}
}