继poj1753继续训练枚举算法:
这道题相比1753有两个改变:
一、从小十字变成了大十字(从改变一个点的上下左右变成了一个点的整行整列),这个倒是不难做,执行函数稍微改一下就行
二、题目直接让你输出改变的点(这道题是special judge),不过我直接把1753的寻找最小步数的思路拿来了,其实只要找到全部为open的一个解就行了
思路差不多,不多解释了,直接上代码(吐槽一下edge,贴代码总是崩溃,google不会崩)
复制代码
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101#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; }
另外说一下,这里我直接用栈存储解,用了后进先出的特点,实际上在dfs用数组存储也是可行的,见别人的题解,直接把16当做dfs参数便于在dfs函数中存储数据
最后
以上就是跳跃黑猫最近收集整理的关于枚举算法思路训练:poj2965的全部内容,更多相关枚举算法思路训练内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复