poj - 2965

跟1753 基本一样， 也就是说，结束条件更严格. 注意输出格式 其实 是 y x (a row number and a column number)

#include <cstdio>  #include <queue>  #include <cstring>  #include <cmath>  #include <string>  #include <stack>  using namespace std;  const int statusNum = 1024*64; //  char initStatus[4][4];  int handleOP[16] = {4383, 8751, 17487, 34959,                  4593, 8946, 17652, 35064,                  7953, 12066, 20292, 36744,                  61713, 61986,  62532, 63624}; // xor  char statusColorMap[statusNum]; // 0: white, 1: grey, 2: black  char statusLevelMap[statusNum];  int statusUpNodeMap[statusNum];  struct move{      int x;      int y;  };  struct move statusMoveMap[statusNum];  // void printStatus(bool status[4][4]) {  //     printf====================================n");  //     for (int i = 0; i <= 3; i++) {  //         for(int j = 0; j <=3; j++) {  //             printf("%d", status[i][j]);  //         }  //         printf("\n");  //     }  //     printf====================================n");  // }  // void handleStatus(bool status[4][4], int i, int j) {  //     status[i][j] = !status[i][j];  //     for (int a = 0; a <= 3; a++) {  //         status[a][j] = !status[a][j];  //     }  //     for (int b = 0; b <= 3; b++) {  //         status[i][b] = !status[i][b];  //     }  // }  // int getStatusId(bool status[4][4]) {  //     int id = 0;  //     for(int i = 0; i <= 3; i++) {  //         for(int j = 0; j <= 3; j++) {  //             id += status[i][j] * pow(2, (j + i*4));  //         }  //     }  //     return id;  // }  int getStatusId(char status[4][4]) {      int id = 0;      for(int i = 0; i <= 3; i++) {          for(int j = 0; j <= 3; j++) {              if (status[i][j] == '+') {                  id += pow(2, (j + i*4));              }          }      }      return id;  }  // void getHandleOP() {  //     bool status[4][4] = {0};  //     for(int i = 0; i <= 3; i++) {  //         for (int j = 0; j <= 3; j++) {  //             memset((void *)status, 0, sizeof(bool)*16);  //             handleStatus(status, i, j);  //             // printStatus(status);  //             printf("%d\n", getStatusId(status));  //         }  //     }  // }  bool isOK(int status) {      if (status == 0) {          return true;      }      return false;  }  void printTrace(int finalStatus) {      int nextStatus = finalStatus;      stack<string> traceStack;      while(statusUpNodeMap[nextStatus] != -1) {          char trace[5] = "";          // printf("%d %d\n", statusMoveMap[nextStatus].x, statusMoveMap[nextStatus].y);          sprintf(trace, "%d %d\n", statusMoveMap[nextStatus].y, statusMoveMap[nextStatus].x);          traceStack.push(string(trace));          nextStatus = statusUpNodeMap[nextStatus];      }      while(!traceStack.empty()) {          printf("%s", traceStack.top().c_str());          traceStack.pop();      }  }  void searchMethod(int status) {      statusUpNodeMap[status] = -1;      statusLevelMap[status] = 0;      statusColorMap[status] = 1;      queue<int> statusNeedToSearch;      statusNeedToSearch.push(status);      while(1) {          if (statusNeedToSearch.size() == 0) {              printf("Impossible\n");              return;          }          int statusToHandle = statusNeedToSearch.front();          statusNeedToSearch.pop();          for(int i = 0; i <= 15; i++) {              int statusAfterHandle = statusToHandle^handleOP[i];              if (statusColorMap[statusAfterHandle] == 0) {                  statusNeedToSearch.push(statusAfterHandle);                  statusColorMap[statusAfterHandle] = 1;                  statusLevelMap[statusAfterHandle] = statusLevelMap[statusToHandle] + 1;                  statusUpNodeMap[statusAfterHandle] = statusToHandle;                  statusMoveMap[statusAfterHandle].x = i%4 + 1;                  statusMoveMap[statusAfterHandle].y = i/4 + 1;                  if (isOK(statusAfterHandle)) {                      printf("%d\n", statusLevelMap[statusAfterHandle]);                      printTrace(statusAfterHandle);                      return;                  }              }          }          statusColorMap[statusToHandle] = 2;      }  }  void handle(int status) {      if (isOK(status)) {          printf("0\n");          return;      }      searchMethod(status);  }  int main() {      // getHandleOP();      for (int i = 0; i <=3; i++) {          scanf("%s", *(initStatus + i));      }      handle(getStatusId(initStatus)); }

果不其然，明显写得明显快了。

或者用位操作快速操作handler数组， 注释部分用于寻求相应的异常或操作数。

除要求操作次数外，本题还要求取出操作步骤，

建造了两个表来保存每个status的最后一个status， 以及status在此status进行的 x y 操作。

在得到最终的status后， 根据这两个表回溯， 最后，添加一个栈来实现顺序输出。

其实这两个表可以合成一个 struct表。

还有， 如果int保存status， 不然溢出。