问题描述
小F被神秘力量带入了一个魔幻世界，这里危机四伏。为了在异世界中生存，小F需要找到安全区。异世界可以被表示为一个大小为 n x m 的二维数组，每个格子的值代表该位置的危险程度。
小F的能力值为 X，当某个格子的危险程度小于等于 X 时，这个格子是安全的。如果多个安全的格子相邻（上下左右连通），它们可以构成一个安全区。你需要帮助小F计算出一共有多少个安全区。
测试样例
样例1：
输入：
n = 3, m = 3, X = 4, a = [[2, 3, 3], [3, 3, 3], [3, 3, 3]]
输出：1
样例2：
输入：
n = 2, m = 2, X = 5, a = [[6, 6], [6, 4]]
输出：1
样例3：
输入：
n = 3, m = 3, X = 3, a = [[1, 2, 2], [2, 3, 3], [3, 4, 5]]
输出：1
题解：
一个原二维数组，新建一个visited数组记录是否经过，直接全部遍历，遇到安全值小于能力值且没经过的点就进入while循环。while循环通过队列实现安全区域的搜寻，通过maxnum记录安全区域的个数。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include <functional>
using namespace std;
typedef long long ll;struct xy{int x=0,y=0;
};int stepx[4]={0,1,0,-1};
int stepy[4]={1,0,-1,0};bool check(int x,int y,int n,int m){if(x>=0 && x<n && y>=0 && y<m){return true;}return false;
}int solution(int n, int m, int X, std::vector<std::vector<int>>& a) {// write code hereint i=0,j=0,k=0,maxnum=1;queue<xy> q;xy num,next;int b[101][101]={{0}};for(i=0;i<n;i++){for(j=0;j<m;j++){if(a[i][j]<=X && b[i][j]==0){num.x=i;num.y=j;q.push(num);while(!q.empty()){num=q.front();q.pop();b[num.x][num.y]=maxnum;///*for(int t1=0;t1<n;t1++){for(int t2=0;t2<m;t2++){cout << b[t1][t2] << " ";}cout << "\n";}cout << "\n";*///cout << num.x << " " << num.y << "\n";for(k=0;k<4;k++){int tx=num.x+stepx[k];int ty=num.y+stepy[k];if(check(tx,ty,n,m) && a[tx][ty]<=X && b[tx][ty]==0){next.x=tx;next.y=ty;q.push(next);}}}maxnum++;}}}//cout << maxnum << "\n";return maxnum-1; // return value is a placeholder
}int main() {std::vector<std::vector<int>> a1 = {{2, 3, 3}, {3, 3, 3}, {3, 3, 3}};std::vector<std::vector<int>> a2 = {{6, 6}, {6, 4}};std::vector<std::vector<int>> a3 = {{1, 2, 2}, {2, 3, 3}, {3, 4, 5}};std::cout << (solution(3, 3, 4, a1) == 1) << std::endl;std::cout << (solution(2, 2, 5, a2) == 1) << std::endl;std::cout << (solution(3, 3, 3, a3) == 1) << std::endl;return 0;
}