枚举算法思路训练：poj2965

54 阅读 0 评论 36 点赞

我是靠谱客的博主跳跃黑猫，最近开发中收集的这篇文章主要介绍枚举算法思路训练：poj2965，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

继poj1753继续训练枚举算法：

这道题相比1753有两个改变：

一、从小十字变成了大十字（从改变一个点的上下左右变成了一个点的整行整列），这个倒是不难做，执行函数稍微改一下就行

二、题目直接让你输出改变的点(这道题是special judge)，不过我直接把1753的寻找最小步数的思路拿来了，其实只要找到全部为open的一个解就行了

思路差不多，不多解释了，直接上代码（吐槽一下edge，贴代码总是崩溃，google不会崩）

#include<stack>
#include<iostream>
using namespace std;

char temp[4][4];
bool jud[4][4];
int temp_min;
int Min = 0x7fffffff;
typedef struct {
	int x;
	int y;
}POINT;
stack<POINT>Q,t;


void change(int n1, int n2) {//改变一个点

	temp[n1][n2] == '+' ? temp[n1][n2] = '-' : temp[n1][n2] = '+';
}
void change_point(int n1, int n2) {//把这个点对应所有改变的点都改变

	for (int i = 0; i < 4; i++) {
		change(n1,i);//把一行的都改了
		change(i,n2);//把一列的改了
	}
	change(n1, n2);//重复的点
}
bool isOk() {//判断是否达成目标，这道题的话可以直接输出结果了，不改了

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++) {
			if (temp[i][j] != '-')//'-'才是打开啊啊啊啊啊啊啊
				return false;
		}
	return true;
}
void dfs(int n1,int n2) {

	if (isOk()) {
		Min = Min < temp_min ? Min : temp_min;
		Q=t;
		return;
	}
	
	if (n2 == 4) {
		dfs(n1 + 1, 0);
		return;
	}
	if (n1 == 4) {
		return;
	}
	
	//动
	if (!jud[n1][n2]) {//没有翻过
		jud[n1][n2] = true;//标记已经翻过
		POINT te = { n1,n2 };//吐槽一下，直接push{n1,n2}交不上去
		t.push(te);//进入队列
		change_point(n1, n2);
		temp_min++;
		dfs(n1, n2 + 1);

		t.pop();
		jud[n1][n2]=false;
		change_point(n1, n2);//状态改回原样
		temp_min--;

	}
	//不动
	dfs(n1, n2 + 1);
}
void Out(stack<POINT>&q) {
	POINT t;
	if (q.size()) {

		t = q.top();
		q.pop();
		Out(q);
		printf("%d %dn", t.x + 1, t.y + 1);
	}
}
int main() {

	int i, j;
	for (i = 0; i < 4; i++) {
		for (j = 0; j <4; j++) {
			scanf("%c", &temp[i][j]);

		}
		getchar();
	}
	dfs(0,0);
	if (Min == 0x7fffffff)		
	cout << "Impossible" << endl;//poj1753带来的，懒得改了，
	//顺道一提，这道题证明了本题中无论4*4矩阵是2^16个情况任意情况都有使其全部为-的解对应
	else {
		cout << Min << endl;
		Out(Q);
	}
	rerurn 0;
}