LC 在他小时候特别迷恋绝地求生，他就幻想着有一天能被扔到一个孤岛，他想算出整个岛屿的面积。

简化题意为一个 n∗n 的地图，共有 n∗n 个面积为 1 格子，地图左上角的格子编号为 (1,1) 右下角的格子编号为为 (n,n) 。地图上为每个格子做了标记，若编号为 (x,y) 的格子标记位 0 则代表这个区域是海，否则为陆地。

现在 LC 空投到 (sx,sy) 位置，他想知道他所在的岛屿的面积。

注意，可能不止一个岛屿，只用求 LC 所在的岛屿面积。

输入格式:

第一行给出一个正整数 n(1<=n<=50) 表示地图的大小为 n∗n

第二行给出两个正整数 sx,sy 表示 LC 空投到的位置

之后的 n 行，每行给出 n 个整数。其中的第 i 行第 j 列的整数若为 0 则代表编号 (i,j) 位置是海洋，否则代表陆地。

保证数据一定合法，且 LC 不会落在海里。

输出格式:

在一行中输出 LC 所在岛屿的面积。

输入样例:

1
2
3
4
5
6
7
8
6
5 3
0 0 0 1 1 0
1 0 0 1 1 0
0 0 1 0 1 1
1 1 0 1 0 1
0 1 1 1 0 1
1 1 0 1 1 1结尾无空行

输出样例:

1
2
3
4
5
19



结尾无空行

思路

从(sx,xy)位置开始广搜，每搜索到一个结点，面积++。每次广搜一个结点时，先分别判断他的上下左右四个结点是否在范围之内，如果没有越界并且没有搜索过，并且可以到达（就是那个位置是岛也就是G[ i ] [ j ]=1），就搜索那个结点。

代码

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
#include<iostream>
#include<queue>
using namespace std;

typedef pair<int,int> PII;

const int maxn=50+5;
int G[maxn][maxn];
int vis[maxn][maxn];

int n;
int deta_x[4]={1,-1,0,0},deta_y[4]={0,0,1,-1};

bool isPosIn(int x,int y)
{
	return x>=1&&y>=1&&x<=n&&y<=n;
}

int bfs(int x,int y)
{
	int res=0;
	queue<PII> que;
	
	vis[x][y]=1;
	res++;
	que.push({x,y});
	
	while(que.size())
	{
		auto curr=que.front();
		que.pop();
		
		for(int i =0;i<4;++i)
		{
			int cx=curr.first+deta_x[i],cy=curr.second+deta_y[i];
			if(isPosIn(cx,cy)&&!vis[cx][cy]&&G[cx][cy])
			{
				que.push({cx,cy});
				vis[cx][cy]=1;
				res++;
			}
		}
	}
	return res;
}
int main()
{
	int sx,sy;
	cin>>n>>sx>>sy;
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cin>>G[i][j];
	cout<<bfs(sx,sy);
}