题目描述，给出一个由01组成的矩阵，任何连在一起的1都看作一块岛，问矩阵中有几个岛

先默写一下BFS的模版

  1. void BFS(int x){
  2.     queue<int> q;
  3.     q.push(x);
  4.     while(!q.empty()){
  5.         int top = q.front;
  6.         q.pop();
  7.         //下一层符合条件的结点入队，并标记已经入队
  8.     }
  9. }

代码

  1. #include<algorithm>
  2. #include<queue>
  3. #include<cstdio>
  4. using namespace std;
  6. const int maxn = 10010;
  8. struct Node{
  9.     int x, y;
  10. }node[maxn];
  12. int n, m, ans = 0;
  13. int matrix[maxn][maxn];
  14. bool inq[maxn][maxn] = {false};
  15. int X[4] = {0, 0, 1, -1};
  16. int Y[4] = {1, -1, 0, 0};
  18. bool judge(int x, int y){
  19.     if(x >= n || y >= m || x < 0 || y < 0 || inq[x][y] == true || matrix[x][y] == 0){
  20.         return false;
  21.     }
  22.     else {
  23.         return true;
  24.     }
  25. }
  27. void BFS(int x, int y){//这道题里的BFS的作用是找出给定节点所在的岛
  28.     queue<Node> q;
  29.     Node temp;
  30.     temp.x = x, temp.y = y;
  31.     q.push(temp);
  32.     inq[x][y] = true;
  33.     while(!q.empty()){
  34.         Node top = q.front();
  35.         q.pop();
  36.         for(int i = 0; i < 4; i++){
  37.             int newx = top.x + X[i];
  38.             int newy = top.y + Y[i];
  39.             if(judge(newx, newy)){
  40.                 inq[newx][newy] = true;
  41.                 temp.x = newx, temp.y = newy;
  42.                 q.push(temp);
  43.             }
  44.         }
  45.     }
  46. }
  48. int main(){
  49.     scanf("%d%d",&n,&m);
  50.     for(int i = 0; i < n; i++){
  51.         for(int j = 0; j < m; j++){
  52.             scanf("%d",&matrix[i][j]);
  53.         }
  54.     }
  55.     for(int i = 0; i < n; i++){
  56.         for(int j = 0; j < m; j++){
  57.             if(inq[i][j]==false && matrix[i][j] == 1){
  58.                 BFS(i, j);
  59.                 ans++;
  60.             }
  61.         }
  62.     }
  63.     printf("%d",ans);
  64. }