8 条题解

  • 3
    @ 2026-5-18 19:24:31

    刚学了博主的并查集，用并查集做了一下

    //#include <iostream>
//#include <queue>
//using namespace std;
//typedef pair<int,int> PII;
//int dx[]={1,0,-1,0};
//int dy[]={0,-1,0,1};
//const int N=510;
//int board[N][N];
//bool stu[N][N];
//int n;
//bool bfs(int x,int y){
//	if(!board[x][y]) return false;
//	if(stu[x][y]) return false;
// 	queue<PII> q;
// 	q.push({x,y});
// 	stu[x][y]=true;
//	while(!q.empty() ){
//		PII temp=q.front() ;
//		q.pop() ;
//		for(int i=0; i<4; i++){
//			int a=temp.first +dx[i],
//				b=temp.second +dy[i];
//			if(a<1 || a>n || b<1 || b>n) continue;
//			if(!board[a][b]) continue;
//			if(stu[a][b]) continue;
//			stu[a][b]=true;
//			q.push({a,b}); 
//		}
//		
//		
//		
//		
//	} 
// 	
//	return true;
//	
//	
//	
//	
//	
//	
//	
//	
//}
//
//
//
//int main()
//{
//	
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cin>>n;
//	for(int i=1; i<=n; i++){
//		for(int j=1; j<=n; j++){
//			cin>>board[i][j];
//		} 
//	}
//	
//	int ans=0;
//	
//	for(int i=1; i<=n; i++){
//		for(int j=1; j<=n; j++){
//			if(bfs(i,j)) ans++;
//		}
//	}
//	cout<<ans<<endl;
//	
//	
//	return 0;
//}








//并查集
#include <iostream>
using namespace std;
const int N=510;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int board[N][N];
int n;
int f[N*N];
int find(int x){
	if(f[x]==x) return x;
	else return f[x]=find(f[x]);
}

void merge(int x,int y){
	x=find(x);
	y=find(y);
	if(x!=y){
		f[y]=x;
	}
}

bool same(int x,int y){
	return find(x)==find(y);
}
//坐标转换 
int change(int x,int y){
	return (x-1)*n+y;
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) {
			cin>>board[i][j];
			f[change(i,j)]=change(i,j);
		}
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(!board[i][j]) continue;
			for(int k=0; k<4; k++){
				int a=i+dx[k],
					b=j+dy[k];
				if(!board[a][b]) continue;
				merge(change(i,j),change(a,b));
			}
		}
	}
	
	int ans=0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(!board[i][j]) continue;
			if(find(change(i,j)) == change(i,j)) ans++;
		}
	}
	
	
	cout<<ans <<endl;
	
	
	return 0;
}
    • 1
      @ 2026-5-28 15:01:38 
      #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
int g[N][N];
bool vis[N][N];
int n;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};

void bfs(int x,int y){
	queue<pair<int,int>> q;
	q.push({x,y});
	vis[x][y] = true;
	
	while(!q.empty()){
		auto it = q.front();
		q.pop();
		int xx = it.first,yy = it.second;
		
		for(int i=0;i<4;i++){
			int nx = xx + dx[i],ny = yy + dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n){
				if(!vis[nx][ny]&&g[nx][ny]==1){
					vis[nx][ny] = true;
					q.push({nx,ny});
				}
			}
		}
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>g[i][j];
		}
	}
    int res=0;
    for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!vis[i][j]&&g[i][j]==1){
				bfs(i,j);
				res++;
			}
		}
	}
    cout<<res;
    return 0;
}
      • 0
        @ 2026-5-27 20:40:58 
        from collections import deque
n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]
count = 0
# 上下左右四个方向
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n):
    for j in range(n):
        if grid[i][j] == 1:
            count += 1
            q = deque([(i, j)])
            grid[i][j] = 0  # 标记为已访问
            while q:
                x, y = q.popleft()
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                        grid[nx][ny] = 0
                        q.append((nx, ny))

print(count)
        • 0
          @ 2026-4-7 16:57:06 
          #include<bits/stdc++.h>
using namespace std;
#define int long long
/* 是一个经典的染色法--（后悔跟y总学的时候跳了） 
  岛屿数量本题可以用DFS/BFS进行写 
  统一思路：1将数组放入1，1开始 但遍历从0，0没有越界考虑
            2 遍历数组找1 直接ans++ 然后进入DFS/BFS进行处理把这部分岛屿全变成海
			本题用BFS写吧  
*/
#define PII pair<int,int>
const int N=550;
int a[N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
int n;
int ans; 
//本题的 BFS/DFS都是解决局部问题即单个岛屿 
void bfs(int x,int y)
{ queue<PII> q;
  a[x][y]=0;//染色
  q.push({x,y});
  while(q.size())
  {
  	auto t=q.front();
  	q.pop();
   int xx=t.first;
   int yy=t.second;  	
  for(int i=0;i<4;i++)
   {
     int nx=xx+dx[i];
	 int ny=yy+dy[i];
	 if(a[nx][ny]==1)
	 {
	   a[nx][ny]=0;
	   q.push({nx,ny});	
	 }	
   }	
  }
  return;
}
signed main()
{ std::ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
	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(a[i][j]==1) 
	 	{
	 	 ans++;
		 bfs(i,j); 	
		}  
   }
	cout<<ans<<"\n"; 	
	return 0;
}
          • 0
            @ 2025-5-25 12:24:31

            蒟蒻的题解，本题主要思路就是：遍历一遍地图，每次遇到了1就dfs把与他相邻的1以及它本身全都搞成0，同时计数器+1 ，这样遍历完一遍岛屿数量也就出来了！！

            //package TemplateQuestion;
import javax.annotation.processing.SupportedSourceVersion;
import java.io.*;
public class Main{ //岛屿的数量   ，看到题目就知道是tmd  DFS了。。.
    static int n;
    static int [][]arr;
    static int count;
    static StreamTokenizer st;
    static PrintWriter pw;
    static int []mx={-1,1,0,0};
    static int []my={0,0,-1,1};
    static void dfs(int a,int b)
    {
        arr[a][b]=0;
      for(int i=0;i<4;i++)
      {
          int tx=a+mx[i];
          int ty=b+my[i];
          if(tx<1||tx>n||ty<1||ty>n||arr[tx][ty]==0)
          {
              continue;
          }
          dfs(tx,ty);
      }
    }
   public static void main(String[] args) throws IOException {
        st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        pw=new PrintWriter(System.out);
        count=0;
        st.nextToken();
        n= (int) st.nval;
        arr=new int[n+1][n+1];
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                st.nextToken();
                arr[i][j]= (int) st.nval;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(arr[i][j]==1)
                {
                    count++;
                    dfs(i,j);
                }
            }
        }
        System.out.println(count);
    }
}
            • 0
              @ 2025-5-11 18:30:49

              如下：

              
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int ans = 0, n;
	static int[][] map;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) {
		solve();
		out.flush();
	}

	static void solve() {
		n = in.nextInt();
		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = in.nextInt();
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == 1) {
					ans++;
					bfs(i, j);
				}
			}
		}
		out.print(ans);

	}

	/**
	 * 第一个版本的BFS
	 * @param x
	 * @param y
	 */
	static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] { x, y });
		map[x][y] = 0;
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int curx = cur[0];
			int cury = cur[1];
			for (int i = 0; i < dx.length; i++) {
				int newx = curx + dx[i];
				int newy = cury + dy[i];
				if (!check(newx, newy) || map[newx][newy] != 1) {
					continue;
				}
				queue.offer(new int[] { newx, newy });
				map[newx][newy] = 0;
			}
		}

	}
	
	/**
	 * 另一个版本BFS
	 * @param x
	 * @param y
	 */
	static void bfs1(int x, int y) {
		Queue<Pair> queue = new LinkedList<>();
		queue.offer(new Pair(x, y));
		map[x][y] = 0;
		while (!queue.isEmpty()) {
			Pair curPair = queue.poll();
			int curx = curPair.x;
			int cury = curPair.y;
			for (int i = 0; i < dx.length; i++) {
				int newx = curx + dx[i];
				int newy = cury + dy[i];
				if (!check(newx, newy) || map[newx][newy] != 1) {
					continue;
				}
				queue.offer(new Pair(newx, newy));
				map[newx][newy] = 0;
			}
		}

	}

	static class Pair {
		int x;
		int y;

		public Pair(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

	}

	/**
	 * DFS版本
	 * @param x
	 * @param y
	 */
	static void dfs(int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int newx = x + dx[i];
			int newy = y + dy[i];
			if (!check(newx, newy)) {
				continue;
			}
			if (map[newx][newy] != 1) {
				continue;
			}
			map[newx][newy] = 0;
			dfs(newx, newy);
		}
	}

	private static boolean check(int newx, int newy) {
		if (newx >= n || newy >= n || newx < 0 || newy < 0) {
			return false;
		}
		return true;
	}

	static FastReader in = new FastReader();
	static PrintWriter out = new PrintWriter(System.out);

	static class FastReader {
		static BufferedReader br;
		static StringTokenizer st;

		FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		Long nextLong() {
			return Long.parseLong(next());
		}
	}
}
            • 0
              @ 2025-5-11 2:11:48

              岛屿的个数

              这题用dfs染色法的思想，可以很快解决，简单来说，就是每次进入dfs时，都把周围的陆地都染色，这样保证了每次进入的都是一个新岛屿 代码如下：

              #include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,mp[N][N],ans;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
bool check(int x,int y){
  return (x>=1&&x<=n&&y>=1&&y<=n&&mp[x][y]==1);
}
void dfs(int x,int y){
  mp[x][y]=2;
  for(int i=0;i<4;i++){
    int cur_x=x+dx[i],cur_y=y+dy[i];
    if(check(cur_x,cur_y)){
      dfs(cur_x,cur_y);
    }
  }
}
int main(){
  cin>>n;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin>>mp[i][j];
    }
  }
  //dfs染色法
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      if(mp[i][j]==1){
        dfs(i,j);
        ans++;
      }
    }
  }
  cout<<ans;
  return 0;
}

              学会了可以试试岛屿个数这道题，也可以用染色法的思想解决～

              • 0
                @ 2025-5-9 19:01:25

                JAVA ac代码:

                package abcd;
import java.util.*;
import java.util.StringTokenizer;
import java.io.*;

public class Main {
	static int n;
	static int[][] a;//矩阵
	static int ans=0;//答案
	static int[] dx= {0,0,-1,1};
	static int[] dy= {1,-1,0,0};
	public static void main(String[] args) {
		n=in.nextInt();
		a=new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				a[i][j]=in.nextInt();
			}
		}
    //遍历图
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
        //当这个点是陆地
				if(a[i][j]==1) {
					ans++;//岛屿数+1
					bfs(i,j);//将相连的陆地全部设置为0
				}
			}
		}
		
		out.println(ans);
		out.close();
	}

	
	

	private static void bfs(int i, int j) {
			
			Queue<int[]> q=new LinkedList<>();
			q.add(new int[]{i,j});//将当前点入队
			//遍历直到周围都是0
			while(!q.isEmpty()) {
				//获得当前相连陆地点的坐标
				int[] temp=q.poll();
				int x=temp[0];
				int y=temp[1];
				//枚举这个坐标上下左右四个点
				for(int k=0;k<4;k++) {
					int x1=x+dx[k];
					int y1=y+dy[k];
					//越界分析和是海洋
					if(x1<0||y1<0||x1>=n||y1>=n||a[x1][y1]==0)continue;
					q.add(new int[] {x1,y1});
					a[x1][y1]=0;//设置为海洋，不再遍历
				}
			}
		
	}




	static FastReader in=new FastReader();
	static PrintWriter out=new PrintWriter(System.out);
	static class FastReader{
		static BufferedReader br;
		static StringTokenizer st;
		FastReader(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			String str="";
			while(st==null||!st.hasMoreElements()) {
				try {
					str=br.readLine();
				}catch(IOException e) {
					throw new RuntimeException(e);
				}
				st=new StringTokenizer(str);
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
}
                • 1

                岛屿的数量

                信息

                ID
                33
                时间
                1000ms
                内存
                256MiB
                难度
                普及−
                标签
                递交数
                443
                已通过
                185
                上传者
                1. Language
                2. 兼容模式
                3. 主题
                3. Worker 0, 17ms
                4. Powered by Hydro v5.0.0-beta.16 Community