2 条题解
-
1
Infinity_ LV 8 @ 9 个月前
坑,说好的1e5,但其实会炸空间,1e3就够了
-
11 年前@
- 1
信息
- ID
- 1243
- 难度
- 5
- 分类
- (无)
- 标签
- 递交数
- 34
- 已通过
- 15
- 通过率
- 44%
- 上传者
坑,说好的1e5,但其实会炸空间,1e3就够了
#include<bits/stdc++.h>
#define N 1100
using namespace std;
bool b[N][N], vis[N][N];
int p[5][3] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}, n;
struct node{
int x, y;
}q[N];
void bfs(int x, int y){
int head = 1, tail = 1;
q[tail].x = x; q[tail].y = y;
tail++;
while(head < tail){
vis[q[head].x][q[head].y] = 1;
for(int i = 0; i < 4; i++){
int nx = q[head].x + p[i][0], ny = q[head].y + p[i][1];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && b[nx][ny] && !vis[nx][ny]){
q[tail].x = nx; q[tail].y = ny; //入队
tail++;
vis[nx][ny] = 1;
}
}
head++; //队头出队
}
}
int main(){
ios::sync_with_stdio(false);
int cnt = 0;
cin >> n;
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++)cin >> b[i][j];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(b[i][j] && !vis[i][j]){
cnt++;
bfs(i, j);
}
}
}
cout << cnt;
return 0;
}
//这题目太坑爹了,说好的1*10^5,结果10^4就够了,1*10^5会爆空间
#include<bits/stdc++.h>
using namespace std;
int n,a[1005][1005],ans;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool vis[1005][1005];
void dfs(int x,int y)
{
vis[x][y]=true;
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(a[nx][ny]==1&&!vis[nx][ny])
{
vis[nx][ny]=true;
dfs(nx,ny);
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(!vis[i][j]&&a[i][j]==1)
{
ans++;
dfs(i,j);
}
}
cout<<ans<<endl;
return 0;
}