学习随笔——POJ题目2965：ThePilotsBrothers'refrigerator解答

本题题目链接：http://poj.org/problem?id=2965

本题前置题目：POJ1753  相关讲解链接：https://www.cnblogs.com/johnsonstar/p/15981589.html

题目截图如下：

思路依然和POJ1753一样是枚举，区别如下：①最终判定条件为所有字符全为“-” ②需要记录经过的点的坐标

关于坐标的记录，本处思路是开辟一个栈和一个最终输出数组来记录坐标。当棋子第一次被翻转，便将坐标压入栈中；当棋子二次翻转（也即复位）后，我们再将坐标弹出。每当最小步数更新时，我们便将临时坐标填入最终输出实现更新。

代码如下：

1 #include
2 #include
3 using namespace std;
4 typedef struct M_Stack{
5 int x_pos[30];
6 int y_pos[30];
7 int num;
8 }M_Stack;
9 M_Stack pos_ans;
10 int mem[16]={0};//记忆化
11 int ans=100;//最终解答
12 int x_ans[30]={0};
13 int y_ans[30]={0};//x坐标与y坐标最终输出
14 int Stack_num=0;
15 void Stack_In (int x,int y){
16 x_ans[Stack_num]=x;
17 y_ans[Stack_num]=y;
18 Stack_num++;
19 }//将栈元素压入
20 void Stack_Out (){
21 Stack_num--;
22 x_ans[Stack_num]=0;
23 y_ans[Stack_num]=0;
24 }//将栈元素弹出
25 void Stack_change (){
26 for (int i=0;i){
27 pos_ans.x_pos[i]=x_ans[i];
28 pos_ans.y_pos[i]=y_ans[i];
29 }
30 pos_ans.num=Stack_num;
31 }//更新栈元素
32 int find_x (int i){
33 return i/4+1;
34 }//坐标转换
35 int find_y (int i){
36 return i%4+1;
37 }//坐标转换
38 void change (int i){
39 int x_pos=i/4;
40 int y_pos=i%4;
41 mem[i % 16] =! mem[i % 16];
42 mem[(i + 4) % 16] = !mem[(i + 4) % 16];
43 mem[(i + 8) % 16] = !mem[(i + 8) % 16];
44 mem[(i + 12) % 16] = !mem[(i + 12) % 16];
45 mem[x_pos * 4 + y_pos % 4] = !mem[x_pos * 4 + y_pos % 4];
46 mem[x_pos * 4 + (y_pos + 1) % 4] = !mem[x_pos * 4 + (y_pos + 1) % 4];
47 mem[x_pos * 4 + (y_pos + 2) % 4] = !mem[x_pos * 4 + (y_pos + 2) % 4];
48 mem[x_pos * 4 + (y_pos + 3) % 4] = !mem[x_pos * 4 + (y_pos + 3) % 4];
49 mem[i] = !mem[i];
50 }//翻转
51 bool Judge (){
52 for (int i=0;i<16;i++){
53 if (mem[i]!=1)
54 return false;
55 }
56 return true;
57 }//判断是否满足终止条件
58 void Enum (int num,int count){
59 if (Judge()){
60 if (count<ans){
61 ans=count;
62 Stack_change();//更新
63 return ;
64 }
65 }
66 if (num>=16)
67 return ;
68 int x_pos=find_x(num);
69 int y_pos=find_y(num);
70 change(num);
71 Stack_In (x_pos,y_pos);//第一次翻转将坐标压入
72 Enum (num+1,count+1);
73 change(num);
74 Stack_Out();//复位将坐标弹出
75 Enum (num+1,count);
76 return ;
77 }
78 int main (int argc,char* argv[]){
79 char temp;
80 for (int i=0;i<16;i++){
81 cin>>temp;
82 if (temp=='-')
83 mem[i]=1;
84 }
85 Enum(0,0);
86 printf("%d\n",ans);
87 for (int i=0;i

)
88 printf("%d %d\n",pos_ans.x_pos[i],pos_ans.y_pos[i]);
89 return 0;
90 }