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"的情況.代碼如下: