简单搜索题解+个人思考+记录

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);
    }
}