posts - 33,  comments - 25,  trackbacks - 0
本题与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, -1sizeof(action_position));
 71     memset(last_action, -1sizeof(last_action));
 72     memset(time, -1sizeof(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>
 2using namespace std;
 3
 4const int ROW = 4;
 5
 6int _tmain(int argc, _TCHAR* argv[])
 7{
 8    bool HANDLES[ROW][ROW] = {false};
 9    char handle;
10    for(int i = 0; i < ROW; ++i)
11    {
12        for(int j = 0; j < ROW; ++j)
13        {
14            cin >> handle;
15            if(handle == '+')
16            {
17                HANDLES[i][j] = !HANDLES[i][j];
18                for(int k = 0; k < ROW; ++k)
19                {
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    {
29        for(int j = 0; j < ROW; ++j)
30        {
31            if(HANDLES[i][j])
32            {
33                ++result;
34            }

35        }

36    }

37    cout << result << endl;
38    for(int i = 0; i < ROW; ++i)
39    {
40        for(int j = 0; j < ROW; ++j)
41        {
42            if(HANDLES[i][j])
43            {
44                cout << i + 1 << " " << j + 1 << endl;
45            }

46        }

47    }

48    return 0;
49}

posted on 2009-03-21 11:11 肖羽思 阅读(3720) 评论(8)  编辑 收藏 引用 所属分类: POJ

FeedBack:
# re: POJ 2965 解题报告
2010-02-15 21:35 | chhaya
高效解法确实很NB啊。  回复  更多评论
  
# re: POJ 2965 解题报告
2010-04-13 20:20 | Cre
我们可以聊一聊吗?不止一次看过你的代码,感觉有必要向你学习一下!  回复  更多评论
  
# re: POJ 2965 解题报告
2010-04-14 10:49 | 肖羽思
@Cre
欢迎交流哈~~学习倒谈不上~~欢迎发邮件至:yusi.xiao@gmail.com  回复  更多评论
  
# re: POJ 2965 解题报告
2010-04-14 22:49 | Cre
@肖羽思
我们可以通过QQ交流吗?感觉这种方式更方便一些!当然,如果你感觉不方便,也无大碍!  回复  更多评论
  
# re: POJ 2965 解题报告
2010-04-15 11:32 | 肖羽思
@Cre
好的~~请加:54118794  回复  更多评论
  
# re: POJ 2965 解题报告
2010-07-05 15:58 | Tanky Woo
按你的写法,似乎输入一个+就改一次,也不论后面的是啥,
个人感觉是错的。要么也是先全部输入后再调整。
不信你输入
++++
+---
+---
+---
应该输出1没错吧?
而你代码的结果是7。
你的意思就是算的有多少个+去了。  回复  更多评论
  
# re: POJ 2965 解题报告
2010-07-05 16:04 | Tanky Woo
还有个地方写错了,那里分别是7次,4次,和2次,
而不是7,6,4次
欢迎去我博客和我探讨:
www.wutianqi.com  回复  更多评论
  
# re: POJ 2965 解题报告
2011-04-18 08:41 | 刘灏
@Tanky Woo
你说的不对,你根本没看楼主的算法,结果必定为1  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜