本题与POJ 1753非常相似,因此直接提交以下代码:
1 #include <iostream>
2 #include <vector>
3 #include <queue>
4 using namespace std;
5
6
7 const int ROW = 4;
8 const int SIZE = ROW * ROW;
9 const int START_ACTION = -2;
10 const int MAX_STATE = 1 << SIZE; // 2 ^ 16
11 const int OPEN = 65535;
12
13 int ConvertCharToInt(char c)
14 {
15 switch(c)
16 {
17 case '+':
18 return 0;
19 case '-':
20 return 1;
21 }
22 return -1;
23 }
24
25 int ChangeState(int state_id, int position)
26 {
27 state_id ^= (1 << position);
28
29 int copy_position = position;
30
31 // left-row
32 int left_end = position / ROW * ROW;
33 while(--copy_position >= left_end && copy_position >= 0)
34 {
35 state_id ^= (1 << copy_position);
36 }
37 copy_position = position;
38
39 // right-row
40 int right_end = (position / ROW + 1) * ROW;
41 while(++copy_position < right_end)
42 {
43 state_id ^= (1 << copy_position);
44 }
45 copy_position = position;
46
47 // up-col
48 int up_end = 0;
49 while((copy_position -= ROW) >= up_end)
50 {
51 state_id ^= (1 << copy_position);
52 }
53 copy_position = position;
54
55 // down-col
56 int down_end = SIZE;
57 while((copy_position += ROW) < SIZE)
58 {
59 state_id ^= (1 << copy_position);
60 }
61 return state_id;
62 }
63
64 int _tmain(int argc, _TCHAR* argv[])
65 {
66 int action_position[MAX_STATE];
67 int last_action[MAX_STATE];
68 int time[MAX_STATE];
69
70 memset(action_position, -1, sizeof(action_position));
71 memset(last_action, -1, sizeof(last_action));
72 memset(time, -1, sizeof(time));
73
74 queue<int> search_query;
75
76 char state;
77 int current_state_id = 0;
78
79 for(int i = 0; i < SIZE; ++i)
80 {
81 cin >> state;
82 current_state_id += ConvertCharToInt(state) << i;
83 }
84
85 if(current_state_id == OPEN)
86 {
87 cout << "0" << endl;
88 return 0;
89 }
90
91 action_position[current_state_id] = START_ACTION;
92 last_action[current_state_id] = START_ACTION;
93 time[current_state_id] = 0;
94
95 search_query.push(current_state_id);
96 int next_state_id;
97
98 while(!search_query.empty())
99 {
100 current_state_id = search_query.front();
101 search_query.pop();
102
103 for(int i = 0; i < SIZE; ++i)
104 {
105 next_state_id = ChangeState(current_state_id, i);
106
107 if(next_state_id == OPEN)
108 {
109 cout << time[current_state_id] + 1 << endl;
110 int result = current_state_id;
111 vector<int> position;
112 position.push_back(i);
113 while(action_position[result] != START_ACTION)
114 {
115 position.push_back(action_position[result]);
116 result = last_action[result];
117 }
118 while(!position.empty())
119 {
120 cout << ((position.back() >> 2) + 1) << " " << (position.back() % 4 + 1) << endl;
121 position.pop_back();
122 }
123 return 0;
124 }
125
126 if(time[next_state_id] == -1 /* not visited */)
127 {
128 action_position[next_state_id] = i;
129 last_action[next_state_id] = current_state_id;
130 time[next_state_id] = time[current_state_id] + 1;
131 search_query.push(next_state_id);
132 }
133 }
134 }
135 return 0;
136 }
结果TLE,至今不知道为什么,两题测试数据相差很大么?
在看了该题的讨论版后,得知一个高效的解法,总结如下:
先看一个简单的问题,如何把'+'变成'-'而不改变其他位置上的状态?答案是将该位置(i,j)及位置所在的行(i)和列(j)上所有的handle更新一次,结果该位置被更新了7次,相应行(i)和列(j)的handle被更新了6次,剩下的被更新了4次.被更新偶数次的handle不会造成最终状态的改变.因此得出高效解法,在每次输入碰到'+'的时候,自增该位置与相应的行和列,当输入结束后,遍历数组,所有为奇数的位置则是操作的位置,而奇数位置的个数之和则是最终的操作次数.
PS:该题不会有"Impossible"的情况.代码如下:
1
#include <iostream>
2
using namespace std;
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
const int ROW = 4;
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
int _tmain(int argc, _TCHAR* argv[])
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
8![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool HANDLES[ROW][ROW] =
{false};
9
char handle;
10
for(int i = 0; i < ROW; ++i)
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
12
for(int j = 0; j < ROW; ++j)
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
14
cin >> handle;
15
if(handle == '+')
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
17
HANDLES[i][j] = !HANDLES[i][j];
18
for(int k = 0; k < ROW; ++k)
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
20
HANDLES[i][k] = !HANDLES[i][k];
21
HANDLES[k][j] = !HANDLES[k][j];
22
}
23
}
24
}
25
}
26
int result = 0;
27
for(int i = 0; i < ROW; ++i)
28![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
29
for(int j = 0; j < ROW; ++j)
30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
31
if(HANDLES[i][j])
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
33
++result;
34
}
35
}
36
}
37
cout << result << endl;
38
for(int i = 0; i < ROW; ++i)
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
40
for(int j = 0; j < ROW; ++j)
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
42
if(HANDLES[i][j])
43![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
44
cout << i + 1 << " " << j + 1 << endl;
45
}
46
}
47
}
48
return 0;
49
}
posted on 2009-03-21 11:11
肖羽思 阅读(3712)
评论(8) 编辑 收藏 引用 所属分类:
POJ