L2-048 寻宝图
题目描述
给定一幅地图,其中有水域,有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏,这些有宝藏的点也被标记出来了。本题就请你统计一下,给定的地图上一共有多少岛屿,其中有多少是有宝藏的岛屿。
输入格式
输入第一行给出
2
2
2个正整数
N
N
N 和
M
M
M
(
1
<
N
×
M
≤
1
e
5
)
(1<N×M≤1e5 )
(1<N×M≤1e5),是地图的尺寸,表示地图由
N
N
N 行
M
M
M 列格子构成。随后
N
N
N 行,每行给出
M
M
M 位个位数,其中
0
0
0 表示水域,
1
1
1 表示陆地,2
-9
表示宝藏。
注意:两个格子共享一条边时,才是“相邻”的。宝藏都埋在陆地上。默认地图外围全是水域。
输出格式
在一行中输出 2 个整数,分别是岛屿的总数量和有宝藏的岛屿的数量。
输入样例
10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001
输出样例
7 2
AC代码文章来源:https://www.toymoban.com/news/detail-430882.html
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int>f[N],st[N];
int cnt,sum;
bool flag;
int n,m;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
void dfs(int x,int y)
{
st[x][y] = true;
if(f[x][y] > 1) flag = true;
for(int i = 0;i < 4;i++)
{
int xx = x + dx[i],yy = y + dy[i];
if(xx >= 1 && xx <= n&&yy >= 1&&yy <= m&&f[xx][yy]&&!st[xx][yy])
{
if(f[xx][yy] > 1) flag = true;
dfs(xx,yy);
}
}
}
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i++)
{
f[i].push_back(0);
st[i].push_back(0);
for(int j = 1;j <= m;j++)
{
char c;
cin>>c;
f[i].push_back(c-'0');
st[i].push_back(0);
}
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
if(f[i][j] && !st[i][j])
{
flag = false;
sum++;
dfs(i,j);
if(flag) cnt++;
}
}
cout<<sum<<" "<<cnt;
return 0;
}
这里需要用vector来存,n*m <= 1e5,二维数组只能开到1e4。
本来想着数据可能很弱,打算直接用二维数组卡过去(/≧▽≦)/,结果被卡了一个点(24分)/(ㄒoㄒ)/~~。
回到这道题,就是一个连通块问题,写个dfs或者bfs就行了,所以这题关键是要想到用vector。文章来源地址https://www.toymoban.com/news/detail-430882.html
到了这里,关于PTA L2-048 寻宝图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!