/*题目大意：有一个最大是15*15的方格，只有黑（1）白（0）构成，当你反转一个的时候，将黑变成白，白变成黑他的四个方向也会跟着反转，现在就是问你怎么反转使得最后的翻转次数最少，假如反转次数相同的话字典序最小。看到这题目瞬间就犯难了，老实说，没有做过。实在不敢花时间深究，，那就只能好好学了。好了， 现在解决两个问题：1、怎么搜索，能够保证搜索完的结果是正确的。这种题目我们不应该从点出发，之前的搜索题我们都是从点出发，这道题我们从每一行进行分析。可以发现假如我们从上到下去搜索的话，这一行的操作完之后，下一行的操作就会受到上一行的影响，他要保证上一行要全为0简单的说，假如上一行已经决定了，那么下一行以及下下一行的操作都可以推出。回过头来，我们从上到下去操作的话，由于一行都受上一行的控制，只有第一行是自由的，所以我们从第一行开始搜起即可。2、如何保证最后的结果字典序最小。这个问题的解决方法就得讲点技巧了，用贪心的方法进行思考，假如我们搜的方法是从字典序由小到大去搜的话，次数小的替换次数大的，相同不替换。这样不就在没有增加复杂度的情况下实现了字典序最小？所以面对这个问题，我们不应该想最后如何去比较，其实一开始就可以解决。好了， 开始吧！*/;int mz[20][20], mmz[20][20], mmmz[20][20],vis[20][20];int Div[4][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };int n, m;void flipped(int x,int y){mmz[x][y] ^= 1;for (int i = 0; i < 4; i++){int tx = x + Div[i][0];int ty = y + Div[i][1];if (tx < 0 || tx >= m || ty < 0 || ty >= n)continue;mmz[tx][ty] ^= 1;}}void output(){for (int i = 0; i < m; i++){printf(“%d”, mmmz[i][0]);for (int j = 1; j < n; j++)printf(” %d”, mmmz[i][j]);puts(“”);}}int main(){while (cin >> m >> n){for (int i = 0; i < m;i++)for (int j = 0; j < n; j++)scanf(“%d”, &mz[i][j]);int MAX = 1 << (m + 1);int ans = 0, res = 0x7ffffff;bool tg = false;for (int i = 0; i < MAX; i++){memcpy(mmz, mz, sizeof(mz));ans = 0;memset(vis, 0, sizeof(vis));for (int j = 0; j < n; j++){int tmp = (i >> j) & 1;vis[0][n – j – 1] = tmp;if (tmp){flipped(0, n – j – 1);ans++;}}for (int j = 1; j < m; j++){if (ans>=res)break;for (int k = 0; k < n;k++){if (mmz[j – 1][k] == 1){flipped(j, k);vis[j][k] = 1;ans++;if (ans>=res)break;}}}if (ans >=res)continue;bool tag = true;for (int j = 0; tag&&j < n;j++)if (mmz[m – 1][j] == 1) tag = false;if (tag){if (ans < res){res = ans;memcpy(mmmz, vis, sizeof(vis));}tg = true;}}if (tg)output();else puts(“IMPOSSIBLE”);}return 0;}
就得加倍付出汗水，赢得场场精彩
