本文主要是介绍POJ 2965 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题我是用最基本的BFS过的。一个简单的优化是每个位置的switch都可以简化为与一个数的异或，这样就不必对该行该列一个个异或了，效率应该能提高一些。
| thestoryofsnow | 2965 | Accepted | 1424K | 750MS | C++ | 2259B |
/*
ID: thestor1
LANG: C++
TASK: poj2965
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;
const int N = 4;int queue[65536];
int visited[65536] = {false};
int previous[65536];
int step[65536][2];bool isOpen(int handler, int r, int c)
{return (handler & (1 << (N * r + c)));
}int switchh(int handler, int r, int c)
{return (handler ^ (1 << (N * r + c)));
}int switchRowCol(int handler, int r, int c)
{for (int i = 0; i < N; ++i){handler = switchh(handler, r, i);}for (int i = 0; i < N; ++i){if (i == r){continue;}handler = switchh(handler, i, c); }return handler;
}void printHandler(int handler)
{printf("[debug]handler(%d):\n", handler);for (int r = 0; r < N; ++r){for (int c = 0; c < N; ++c){if (isOpen(handler, r, c)){printf("+");}else{printf("-");}}printf("\n");}
}int main()
{int handler = 0;char line[N + 1];for (int r = 0; r < N; ++r){scanf("%s", line);for (int c = 0; c < N; ++c){if (line[c] == '+'){handler |= 1 << (N * r + c);}}}queue[0] = handler;int front = 0, rear = 1;visited[handler] = true;int nh;while (front < rear){int h = queue[front];front++;if (h == 0){break;}for (int r = 0; r < N; ++r){for (int c = 0; c < N; ++c){nh = switchRowCol(h, r, c);if (!visited[nh]){previous[nh] = h;step[nh][0] = r;step[nh][1] = c;queue[rear] = nh;rear++;visited[nh] = true;// printf("\n");// printHandler(h);// printf("---------->\n");// printHandler(nh);// printf("\n");}}}}// printHandler(handler);int h = 0;std::vector<pair<int, int> > steps;while (h != handler){// printHandler(h);steps.push_back(make_pair(step[h][0], step[h][1]));h = previous[h];}printf("%lu\n", steps.size());for (int i = steps.size() - 1; i >= 0; --i){printf("%d %d\n", steps[i].first + 1, steps[i].second + 1);}return 0;
}这篇关于POJ 2965 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
