制作公司网站 黑龙江,网络规划设计师待遇怎么样,网站购买,搜狗seo查询1. 数字操作 常见的模板 // 使用一个数组判断元素是否入过队 int inqueue[N] {0}; // 层数或者可以称为深度 int step 0; // 判断是否可以入队的条件 int isvalid(){ } BFS(int x){ // 将初始的元素压入队列 // 注意每次压队的时候都要将inque[x] 1,表明入队过… 1. 数字操作 常见的模板 // 使用一个数组判断元素是否入过队 int inqueue[N] {0}; // 层数或者可以称为深度 int step 0; // 判断是否可以入队的条件 int isvalid(){ } BFS(int x){ // 将初始的元素压入队列 // 注意每次压队的时候都要将inque[x] 1,表明入队过 queueint q; q.push(x); inqueue[x] 1; //大循环 队列q不为空 while (!q.empty()){ // 获得这一层的所有元素 因为咱们是广度优先 int cnt q.size(); //小循环 while (cnt--){ int temp q.front(); q.pop(); // BFS寻找的目的,这里就是temp 是否 n if (temp n){ return ;//视情况而定 } // 以此节点开始寻找下一层的有效节点 if (isvalid(temp1)){ q.push(temp1); // 注意压队就要伴随着inqueue[]的变化 inqueue[temp1] 1; } // ....同理 } // 在小循环结束后意味着整层的元素都被遍历过了若没有则下一层 step; } } #include cstdio
#include queue
using namespace std;
const int N 1e510;
int n;
int inqueue[N] {0};
int isvalid(int x){if (xn inqueue[x] 0)return 1;else return 0;
}
int step 0;
void BFS(){ queueint q;q.push(1);inqueue[1] 1;while (!q.empty()){int cnt q.size();while (cnt--){int temp q.front();q.pop();if (temp n){return;}if (isvalid(temp1)){q.push(temp1);inqueue[temp1] 1;}if (isvalid(temp*2)){q.push(temp*2);inqueue[temp*2] 1;}}step;}
}
int main(){scanf(%d,n);BFS();printf(%d,step);return 0;
}
2. 矩阵的块 题目的思路很简单首先就是从头到尾遍历数组当遇到1并且未如过队证明其是一个全新的块时进行BFS直到周围都是0无法进展为止在BFS过程中遍历过的1都被压入队中因此inqueue为1那么经过几次BFS证明就有几个块。
#include cstdio
#include queue
#include utilityusing namespace std;
// 由于需要压队那么队内的元素为PII
typedef pairint,int PII;const int N 110;
int n,m;
// 是否入队位置用二维数组即可
int inqueue[N][N] {0};// 存储整个矩阵
int A[N][N];// 块的数量
int count 0;// 为了便于上下左右的移动可以设置两个数组表示上下左右的变量
int dx[4] {-1,1,0,0};
int dy[4] {0,0,-1,1};int isvalid(int x,int y){// 有效的压队条件x,y未逾越矩阵的范围未入过队并且值为1if (x1 xn y1 ym inqueue[x][y] 0 A[x][y] 1)return 1;else return 0;
}
void BFS(int i,int j){queuePII q;q.push(make_pair(i,j));inqueue[i][j] 1;while (!q.empty()){int cnt q.size();while (cnt--){PII temp q.front();q.pop();// 我们无需返回什么因此这里不需要写return 的语句// 开始寻找下一个有效的节点for (int i0;i4;i){int nextx temp.firstdx[i];int nexty temp.seconddy[i];if (isvalid(nextx,nexty)){q.push(make_pair(nextx,nexty));inqueue[nextx][nexty] 1;}}}}
}
int main(){scanf(%d%d,n,m);for (int i1;in;i)for (int j1;jm;j)scanf(%d,A[i][j]);for (int i1;in;i)for (int j1;jm;j)if (A[i][j] 1 inqueue[i][j] 0){BFS(i,j);count;}printf(%d,count);return 0;
}
