poj.1753dfs

103 阅读 0 评论 68 点赞

我是靠谱客的博主勤劳蜜粉，这篇文章主要介绍poj.1753dfs，现在分享给大家，希望可以做个参考。

这道题的意思很简单，主要需要注意的有两点，第一：矩阵中的每个点都最多被主动翻一次，（注意不是被动），所以总共有2^16种可能，只要枚举每种可能了。第二：翻转的顺序对结果没有影响，所以问题的关键就在于那些点被主动翻转了。翻转多少次就有多少次round,只要求出所有round中最小的一个就是答案了，如果没有一种可能可以得到结果则输出“Impossible"。下面是代码和测试数据：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//#include <iostream>
#include <stdio.h>
#include <stdlib.h>
//using namespace std;
#define Inf 1000000
int maxn;
int s[4][4];
void Init(){
	char ch[4][4];
	int i,j;
	for(i=0;i<4;i++)
		scanf("%s",ch[i]);
	for(i=0;i<4;i++)
		for(j=0;j<4;j++){
			if(ch[i][j]=='b')
				s[i][j]=1;
			else
				s[i][j]=-1;
		}
		/*for(i=0;i<4;i++)
			for(j=0;j<4;j++)
             printf("%d ",s[i][j]);*/
}	
bool Is_right(int (*t)[4]){
	int i,j;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			if(t[i][j]!=t[0][0])
				return false;
			return