P1123 取数游戏

题目描述

一个 $N\times M$ 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 $8$ 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

输入格式

第一行有一个正整数 $T$，表示了有 $T$ 组数据。

对于每一组数据，第一行有两个正整数 $N$ 和 $M$，表示了数字矩阵为 $N$ 行 $M$ 列。

接下来 $N$ 行，每行 $M$ 个非负整数，描述了这个数字矩阵。

输出格式

共 $T$ 行，每行一个非负整数，输出所求得的答案。

输入输出样例 #1

输入 #1

3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1

输出 #1

271
172
99

说明/提示

样例解释

对于第一组数据，取数方式如下：

$$\begin{matrix} [67] & 75 & 63 & 10 \\ 29 & 29 & [92] & 14 \\ [21] & 68 & 71 & 56 \\ 8 & 67 & [91] & 25 \\ \end{matrix}$$

数据范围及约定

• 对于$20\%$的数据，$1\le N, M \le 3$；
• 对于$40\%$的数据，$1\le N, M\le 4$；
• 对于$60\%$的数据，$1\le N, M\le 5$；
• 对于$100\%$的数据，$1\le N, M\le 6$，$1\le T\le 20$，$a_{i,j}\le10^5$。

排列问题

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
int a[10][10];
int flag[10][10];
int ans;
void b8(int x,int y){
	flag[x-1][y-1]++;
	flag[x-1][y]++;
	flag[x-1][y+1]++;
	flag[x][y-1]++;
	flag[x][y+1]++;
	flag[x+1][y-1]++;
	flag[x+1][y]++;
	flag[x+1][y+1]++;
	return;
}
void q8(int x,int y){
	flag[x-1][y-1]--;
	flag[x-1][y]--;
	flag[x-1][y+1]--;
	flag[x][y-1]--;
	flag[x][y+1]--;
	flag[x+1][y-1]--;
	flag[x+1][y]--;
	flag[x+1][y+1]--;
	return;
}

void pf(int x,int y,int s){// 打印中间值
	cout<<"dfs"<<x<<" "<<y<<" "<<s<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<flag[i][j]<<" ";
		}
		cout<<endl;
	}
}

void dfs(int x,int y,int s){//取出x行y列这个点上的数
	//取数操作
	flag[x][y]=100;//标记被取出的数字
	b8(x,y);//标记这个数字相邻的数字
//	pf(x,y,s);
	// 边界条件，所有可能的点都考虑过
	// 如果所有的数字都被标记，就结束递归
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(flag[i][j]!=0)cnt++;
		}
	}
//	cout<<cnt<<endl;
	if(cnt==n*m){
		ans = max(ans,s+a[x][y]);
//		cout<<"ans!!!!!!:::"<<ans<<endl;
		return;
	}
	// 分层遍历所有可能性
	

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(flag[i][j]==0){
				dfs(i,j,s+a[x][y]);
				flag[i][j]=0;
				q8(i,j);
			}
		}
	}
	
	return;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		memset(flag,0,sizeof(flag));
		ans = 0;
		dfs(9,9,0);
		cout<<ans<<endl;
	}
	return 0;
}

组合问题

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
int a[10][10];
int flag[10][10];
int ans;
void b8(int x,int y){
	flag[x-1][y-1]++;
	flag[x-1][y]++;
	flag[x-1][y+1]++;
	flag[x][y-1]++;
	flag[x][y+1]++;
	flag[x+1][y-1]++;
	flag[x+1][y]++;
	flag[x+1][y+1]++;
	return;
}
void q8(int x,int y){
	flag[x-1][y-1]--;
	flag[x-1][y]--;
	flag[x-1][y+1]--;
	flag[x][y-1]--;
	flag[x][y+1]--;
	flag[x+1][y-1]--;
	flag[x+1][y]--;
	flag[x+1][y+1]--;
	return;
}

void pf(int x,int y,int s){// 打印中间值
	cout<<"dfs"<<x<<" "<<y<<" "<<s<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<flag[i][j]<<" ";
		}
		cout<<endl;
	}
}

void dfs(int x,int y,int s){//上一个被选的点是谁,s代表已经取出数字之和

	pf(x,y,s);
	// 边界条件，基于上一个点xy选不出下一个点时代表找完所有点
	
	// 如果所有的数字都被标记，就结束递归

	// 分层遍历下一个点所有可能性
	// 下一个点同行
	bool shifou = false;
	for(int j=y+1;j<=m;j++){
		if(flag[x][j]==0){
			//取数操作
			shifou =true;
			flag[x][j]=100;//标记被取出的数字
			b8(x,j);//标记这个数字相邻的数字
			dfs(x,j,s+a[x][y]);
			flag[x][j]=0;
			q8(x,j);
		}
	}
	for(int i=x+1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(flag[i][j]==0){
				//取数操作
				shifou =true;
				flag[x][y]=100;//标记被取出的数字
				b8(x,y);//标记这个数字相邻的数字
				dfs(i,j,s+a[x][y]);
				flag[i][j]=0;
				q8(i,j);
			}
		}
	}
	if(shifou == false){//没有新的取数机会了
		ans = max(ans,s);
	}
	return;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		memset(flag,0,sizeof(flag));
		ans = 0;
		dfs(1,0,0);
		cout<<ans<<endl;
	}
	return 0;
}

01枚举

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
int a[10][10];
int flag[10][10];
int ans;
void b9(int x,int y){
	flag[x][y]++;
	flag[x-1][y-1]++;
	flag[x-1][y]++;
	flag[x-1][y+1]++;
	flag[x][y-1]++;
	flag[x][y+1]++;
	flag[x+1][y-1]++;
	flag[x+1][y]++;
	flag[x+1][y+1]++;
	return;
}
void q9(int x,int y){
	flag[x][y]--;
	flag[x-1][y-1]--;
	flag[x-1][y]--;
	flag[x-1][y+1]--;
	flag[x][y-1]--;
	flag[x][y+1]--;
	flag[x+1][y-1]--;
	flag[x+1][y]--;
	flag[x+1][y+1]--;
	return;
}

void pf(int x,int y,int s){// 打印中间值
	cout<<"dfs"<<x<<" "<<y<<" "<<s<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<flag[i][j]<<" ";
		}
		cout<<endl;
	}
}

void dfs(int x,int y,int s){//取出x行y列这个点上的数,s代表已经取出数字之和
	//边界条件
	if(x>n){
		ans = max(ans,s);
		return;
	}
	//判断这个点是否合法
	if(y>m){
		//换到下一行
		dfs(x+1,1,s);
		return;
	}
	//取x,y点数据
	if(flag[x][y]==0){
		b9(x,y);//标记
		dfs(x,y+1,s+a[x][y]);
		q9(x,y);//取消标记
	}
	//不取
	dfs(x,y+1,s);
	return;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		memset(flag,0,sizeof(flag));
		ans = 0;
		dfs(1,1,0);
		cout<<ans<<endl;
	}
	return 0;
}