实验四：搜索

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;queue<int>x;//初始化队列x来存储横坐标
queue<int>y;//初始化队列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;cin>>N;for(int i=1;i<=N;i++){//从数组的索引1位置开始输入，外圈补一圈0for(int j=1;j<=N;j++){cin>>matrix[i][j];}}x.push(0);//将（0，0）坐标入队列y.push(0);visited[0][0]=1;int x1,y1;while(!x.empty()){for(int i=0;i<4;i++){//遍历对应元素的上下左右位置x1 = x.front()+delta_x[i];y1 = y.front()+delta_y[i];//如果满足没有越界且是0元素且没有被访问过if(x1>=0 && x1<=N+1 && y1>=0 && y1<=N+1 && matrix[x1][y1]==0 && visited[x1][y1]==0){x.push(x1);//则将对应的元素入队y.push(y1);visited[x1][y1]=1;}  }x.pop();y.pop();}for(int p=1;p<=N;p++) {for(int q=1;q<=N;q++) {if(visited[p][q]==0 && matrix[p][q]==0){//如果元素没有被访问过，且为0元素cout<<2<<' '; }else{cout<<matrix[p][q]<<' '; } }cout<<endl;}return 0;
}

2.N皇后

题目描述

N皇后的排列，每行一个不冲突；N<=13。

输入要求

一个数字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 i=1;i<p;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 p=1,ans=0,count=1;result[p]=1;//初始化：从第一行第一列开始放while(p>0){//对于第p行来说if(p<=n && result[p]<=n){//如果行列都没有超出矩阵范围if(is_place(p)==0){//当前列不合法result[p]=result[p]+1;//放到下一个位置}else{//当前列合法p=p+1;//到下一列去result[p]=1;//下一列从1开始}}else{//如果行列超出了索引范围,回溯if(p>n){//得到一个正确答案ans=ans+1;//正确答案数目加1if(count<=3){for(int j=1;j<n;j++){//输出一条正确答案cout<<result[j]<<" ";}cout<<result[n];cout<<endl;count++;}}p=p-1;//回到上一行result[p]=result[p]+1;//上一行的棋子往右走}}cout<<ans<<endl;
}
int main() 
{int N;cin>>N;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

#include<iostream>
#include<cstring>using 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(x<0 || x>n+1 || y<0 || y>n+1 || a[x][y]!=0)  //禁止染色的判断 x<0 || x>n+1 || y<0 || y>n+1为矩阵4个边return ;a[x][y] = id;  //染色cnt++;for(int i=0; i<4; i++){dfs(x+dir[i][0], y+dir[i][1]);} 
}
int main()
{cin >> n;memset(a, 0, sizeof(a)); int i;// 输入数据 for( i=1; i<=n; i++)for(int j=1; j<=n; j++){int k;cin >> k;a[i][j] = k;}//将边缘的0和其连接块都染色dfs(0, 0);id++;for( i=2; i<n; i++)for(int j=2; j<n; j++){cnt = 0;// 搜索每一个元素，找到最大封闭区域 dfs(i, j);//cout << cnt;if(cnt > maxn){maxn = cnt;max_id = id;}id++;}
// 输出	
for( i=1; i<=n; i++)
{for(int j=1; j<=n; 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种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色。运用回溯法解决该问题。

输入要求

顶点数 颜色数

邻接矩阵

输出要求

着色方案

输入样例

输出样例

#include<iostream>
#include<stdio.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 i=1;i<=k;i++){if(c[k][i]==1&&color[i]==color[k]) //k与i之间相连并且i顶点的颜色与k顶点的颜色相同return 0;}return 1;
}
void GraphColor(int step)
{if(step==n+1)  //表示前面所有的顶点颜色都已经填完{for(int i=1;i<=n;i++)printf("%d ",color[i]);count++;printf("\n");return ;}else{for(int i=1;i<=m;i++){color[step]=i;   //首先将这个顶点颜色换为iif(Check(step)==1)  //检查是否符合条件{GraphColor(step+1); //符合条件则走下一步}color[step]=0;  //回溯 置为0}}
}
int main(void)
{printf("请输入顶点数：");scanf("%d",&n);printf("\n");printf("请输入颜色数：");scanf("%d",&m);printf("\n");printf("请输入邻接矩阵：\n");for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>c[i][j];}printf("\n方案如下：\n");GraphColor(1);printf("\n");printf("%d",count);return 0;
}