简单搜索题解+个人思考+记录
简单搜索题解+个人思考+记录
A - 棋盘问题
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1
Sample Output
2
1
一道DFS题，给一个n级矩阵,k个棋子,限制条件为每行每列只能放一个棋子。因此我们可以每行每行的搜索，看成一个n层树，找到一个可行结点后搜索下一层，若找不到返回上一层继续搜索。代码+注释如下。
#include<bits/stdc++.h>
using namespace std;
char mp[10][10];//绘制地图
int vis[10];//因为从每行搜，所以只需标记每列是否被访问
int r,c,n,k,sum;//行，列，矩阵大小，棋子个数,方案总和
void dfs(int r,int w){ //r表示搜索当前行，w表示为当前放棋子个数
if(w>=k)//终止条件，如果放完所有棋子，方案数+1
{
sum++;//！！！！！此处if(里面两个语句应该大括号，没输大括号导致WA
return;
}
for(int i=r;i<n;i++)
for(int j=0;j<n;j++)
{
if(!vis[j]&&mp[i][j]=='#')
{
vis[j]=1;//放置该棋子后该列标记
dfs(i+1,w+1);//！！！！此处应该是搜索i+1行，而不是r+1
vis[j]=0;//清楚标记，防止下次访问再放置该列
}
}
return;
}
int main(){
while(cin>>n>>k)
{
if(n==-1&&k==-1) break;
memset(vis,0,sizeof(vis));//每次输入一组数据就将其初始化
memset(mp,0,sizeof(mp));
for(int i=0;i<n;i++)
cin>>mp[i];
sum=0;
dfs(0,0);
cout<<sum<<endl;
}
return 0;
}
B-石油采集
随着海上运输石油泄漏的问题，一个新的有利可图的行业正在诞生，那就是撇***业。如今，在墨西哥湾漂浮的大量石油，吸引了许多商人的目光。这些商人们有一种特殊的飞机，可以一瓢略过整个海面20米乘10米这么大的长方形。（上下相邻或者左右相邻的格子，不能斜着来）当然，这要求一瓢撇过去的全部是油，如果一瓢里面有油有水的话，那就毫无意义了，资源完全无法利用。现在，商人想要知道，在这片区域中，他可以最多得到多少瓢油。
地图是一个N×N的网络，每个格子表示10m×10m的正方形区域，每个区域都被标示上了是油还是水
Input
测试输入包含多条测试数据
测试数据的第一行给出了测试数据的数目T（T<75）
每个测试样例都用数字N（N<50）来表示地图区域的大小，接下来N行，每行都有N个字符，其中符号’.’表示海面、符号’#’表示油面。
Output
输出格式如下“Case X: M”（X从1开始），M是商人可以最多得到的油量。
示例1
输入
1
6
......
.##...
......
.#..#.
.#..##
......
输出
Case 1: 3
一个DFS+数学题，一个n级矩阵，找到最大油量，建立x-y坐标系，易知上下左右相邻两点坐标之和必为一奇一偶，即一个油量必须包含两个坐标和为一奇一偶的点，由下图知，取奇数和偶数的最小值即为油量数
代码如下
#include<bits/stdc++.h>
using namespace std;
char s[60][60];
int odd,even,n;
void dfs(int x,int y){
if (x>=n||y>=n||x<0||y<0||s[x][y]=='.') return;//越界或者无油则返回
(x+y)&1?++odd:++even;//如果x+y和为奇数则odd++，偶数even++;
s[x][y]='.';//标记
dfs(x+1,y);//四个方向搜索
dfs(x-1,y);
dfs(x,y+1);
dfs(x,y-1);
}
int main(){
int t,kase=0;
cin>>t;
while(t--){
scanf("%d",&n);
int ans=0;
for (int i=0; i<n; ++i) cin>>s[i];//绘图
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
if (s[i][j]=='#'){
odd=even=0;//每次都要初始化
dfs(i,j);
ans+=min(odd,even);
}
printf("Case %d: %d\n",++kase,ans);
}
}
