商机互联做网站怎么样,vue.js2.5 pc网站开发,网站服务器网络,国内哪个搜索引擎最好用实验四#xff1a;搜索
1.填格子
题目描述
有一个由数字 0、1 组成的方阵中#xff0c;存在一任意形状的封闭区域#xff0c;封闭区域由数字1 包围构成#xff0c;每个节点只能走上下左右 4 个方向。现要求把封闭区域内的所有空间都填写成2
输入要求
每组测试数据第一…实验四搜索
1.填格子
题目描述
有一个由数字 0、1 组成的方阵中存在一任意形状的封闭区域封闭区域由数字1 包围构成每个节点只能走上下左右 4 个方向。现要求把封闭区域内的所有空间都填写成2
输入要求
每组测试数据第一行一个整数 n(1≤n≤30)
接下来 n 行由 0 和 1 组成的 n×n 的方阵。
封闭区域内至少有一个0 。
输出要求
已经填好数字 2 的完整方阵。
注意矩阵的每个数字后面都有一个空格
输入样例
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
输出样例
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
#include iostream
#include queue
using namespace std;queueintx;//初始化队列x来存储横坐标
queueinty;//初始化队列y来存储纵坐标int matrix[31][31];
int visited[31][31]{0};//visited用来记录元素是否被访问过int delta_x[4]{0,-1,0,1};//delta_x和delta_y用来进行广搜来搜索对应元素的上下左右
int delta_y[4]{1,0,-1,0};int main()
{int N;cinN;for(int i1;iN;i){//从数组的索引1位置开始输入外圈补一圈0for(int j1;jN;j){cinmatrix[i][j];}}x.push(0);//将00坐标入队列y.push(0);visited[0][0]1;int x1,y1;while(!x.empty()){for(int i0;i4;i){//遍历对应元素的上下左右位置x1 x.front()delta_x[i];y1 y.front()delta_y[i];//如果满足没有越界且是0元素且没有被访问过if(x10 x1N1 y10 y1N1 matrix[x1][y1]0 visited[x1][y1]0){x.push(x1);//则将对应的元素入队y.push(y1);visited[x1][y1]1;} }x.pop();y.pop();}for(int p1;pN;p) {for(int q1;qN;q) {if(visited[p][q]0 matrix[p][q]0){//如果元素没有被访问过且为0元素cout2 ; }else{coutmatrix[p][q] ; } }coutendl;}return 0;
}2.N皇后
题目描述
N皇后的排列每行一个不冲突N13。 输入要求
一个数字N (6 N 13) 表示棋盘是N x N大小的。
输出要求
前三行为前三个解每个解的两个数字之间用一个空格隔开。第四行只有一个数字表示解的总数。
解的输出顺序为从上到下从左到右小的优先输出
输入样例
6
输出样例
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
#include iostream
#include cmath
using namespace std;
//用result来保存结果result[i]p表示棋子放在第i行第p列
int result[15];
//定义一个函数用来判断棋子放在当前行第p列是否合法
int is_place(int p)
{for(int i1;ip;i){//对于前面p-1行来说if((result[i]result[p]) || (abs(result[i]-result[p])abs(i-p))){//不合法情况在同一列或者在斜线上return 0;}}return 1;
}
// 定义函数求解N皇后问题
void Queen(int n)
{int p1,ans0,count1;result[p]1;//初始化从第一行第一列开始放while(p0){//对于第p行来说if(pn result[p]n){//如果行列都没有超出矩阵范围if(is_place(p)0){//当前列不合法result[p]result[p]1;//放到下一个位置}else{//当前列合法pp1;//到下一列去result[p]1;//下一列从1开始}}else{//如果行列超出了索引范围,回溯if(pn){//得到一个正确答案ansans1;//正确答案数目加1if(count3){for(int j1;jn;j){//输出一条正确答案coutresult[j] ;}coutresult[n];coutendl;count;}}pp-1;//回到上一行result[p]result[p]1;//上一行的棋子往右走}}coutansendl;
}
int main()
{int N;cinN;Queen(N);return 0;
}3.再填格子
题目描述
有一个由数字 0、1 组成的方阵中存在一任意形状的封闭区域封闭区域由数字1 包围构成每个节点只能走上下左右 4 个方向。现要求只把**【最大封闭区域】**内的空间填写成2 。
例如 6×6 的方阵
6 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1
填写后如下
0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1
输入要求
每组测试数据第一行一个整数 n(1≤n≤30)
接下来 n 行由 0 和 1 组成的 n×n 的方阵。
封闭区域内至少有一个0测试数据保证最大区域只有一个。
输出要求
已经填好数字 2 的完整方阵。(每个数字后面有一个空格
输入样例
6 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1
输出样例
0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1
#includeiostream
#includecstringusing namespace std;
int a[40][40];
int n;
int dir[4][2] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 右 左 下 上
int cnt 0; // 某一个封闭区域的大小
int maxn 0; // 最大封闭区域大小
int id 3; // 染色区域的编号
int max_id id;
void dfs(int x, int y)
{if(x0 || xn1 || y0 || yn1 || a[x][y]!0) //禁止染色的判断 x0 || xn1 || y0 || yn1为矩阵4个边return ;a[x][y] id; //染色cnt;for(int i0; i4; i){dfs(xdir[i][0], ydir[i][1]);}
}
int main()
{cin n;memset(a, 0, sizeof(a)); int i;// 输入数据 for( i1; in; i)for(int j1; jn; j){int k;cin k;a[i][j] k;}//将边缘的0和其连接块都染色dfs(0, 0);id;for( i2; in; i)for(int j2; jn; j){cnt 0;// 搜索每一个元素找到最大封闭区域 dfs(i, j);//cout cnt;if(cnt maxn){maxn cnt;max_id id;}id;}
// 输出
for( i1; in; i)
{for(int j1; jn; j){if(a[i][j] 1)cout a[i][j] ;else if(a[i][j] ! max_id)cout 0 ;else cout 2 ;} cout endl;}return 0;
}4.地图着色
题目描述
地图着色问题如果把每一个区域收缩为一个顶点把相邻两个区域用一条边相连接就可以把一个区域图抽象为一个平面图。用m种颜色为图中的每个顶点着色要求每个顶点着一种颜色并使相邻两顶点之间有着不同的颜色。运用回溯法解决该问题。
输入要求
顶点数 颜色数
邻接矩阵
输出要求
着色方案
输入样例 输出样例 #includeiostream
#includestdio.h
using namespace std;
int c[100][100]; //邻接矩阵
int color[100]; //记录每个顶点的颜色
int count,m,n; //count记录方案数 n个顶点 m种颜色
int Check(int k) //检查第i个顶点的颜色是否满足条件
{for(int i1;ik;i){if(c[k][i]1color[i]color[k]) //k与i之间相连并且i顶点的颜色与k顶点的颜色相同return 0;}return 1;
}
void GraphColor(int step)
{if(stepn1) //表示前面所有的顶点颜色都已经填完{for(int i1;in;i)printf(%d ,color[i]);count;printf(\n);return ;}else{for(int i1;im;i){color[step]i; //首先将这个顶点颜色换为iif(Check(step)1) //检查是否符合条件{GraphColor(step1); //符合条件则走下一步}color[step]0; //回溯 置为0}}
}
int main(void)
{printf(请输入顶点数);scanf(%d,n);printf(\n);printf(请输入颜色数);scanf(%d,m);printf(\n);printf(请输入邻接矩阵\n);for(int i1;in;i)for(int j1;jn;j){cinc[i][j];}printf(\n方案如下\n);GraphColor(1);printf(\n);printf(%d,count);return 0;
}
