题目描述

恭喜我的题解来到第二期，我会加油的

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 所在岛屿的面积。

输入样例:
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
输出样例:
19
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB

样例

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

19

算法1

(深搜) $O(nm)$

又是一道深搜模拟题

时间复杂度

$O(nm)$

参考文献

无

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,sx,sy,ex,ey;
int ditu[105][105];
bool used[105][105];
int dx[]={0,-1,1,0,0};
int dy[]={0,0,0,-1,1};
void dfs(int x,int y)
{
        for (int i=1;i<=4;i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx<1 || nx>n || ny<1 || ny>n)
               continue;
            if (ditu[nx][ny]!=0 && used[nx][ny]!=1)
            {
                used[nx][ny] = 1;
                cnt++;
                dfs(nx,ny);
            } 
        }
}
int main()
{
    cin>>n;
    cin>>sx>>sy;
    for(int i=1;i<=n;i++)           
        for(int j=1;j<=n;j++)
            cin>>ditu[i][j];
    used[sx][sy]=1; 
    dfs(sx,sy);
    cout<<cnt+1;
}