分类 POJ 下的文章


题意

题目中的意思是,给出一个由 0 和 1 组成的矩阵块,每次按压之后,按压的那一块,其上下左右四面的块的状态都会改变状态,问哪一种按压方法,可以在按压的次数最少的情况下使得矩阵全部为 0,最后输出矩阵。

思路

这个在操作的时候,每一个块一定要尽可能的少操作,因为操作偶数次会恢复初始状态,并且由题意知道,操作的顺序对解结果没有影响,所以我们可以先给定第一行的状态,再由第一行去逐一判断下一行,直到最后看一看是不是合法就好了。


这里的第一行的操作的枚举,可以使用二进制来进行,快速方便,简记做如下代码:

for(int i = 0;i < (1<<n); ++i){
    memset(jge,0,sizeof(jge));
    for(int j = 0;j < n; ++j){
        jge[0][n-j-1] = i>>j&1;
    }
}

有这几行代码给出的数组的第一行,就是不同的操作状态,也就是每一种我们都去模拟一下,最后看看哪一个最小。


  • find 函数用于查询和合法性检验,给出经过当前所有已有的操作后,此块是否变为 0 的检验。
  • js 函数用于计算,给出某一个 块 是否按压的记录,并且检查当前的操作是否合法,不合法就输出 IMPOSSIBLE ,否则累加当前状态的操作数,看看是不是当前最优操作。
  • filp 函数是主体函数,给出模拟状态,判断最优解是否存在,输出结果。
    大体就这么个思路,下面给出代码。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <functional>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <climits>
typedef long long ll;
using namespace std;
const int maxn = 100;
const int dx[5] = {-1,0,0,0,1};
const int dy[5] = {0,-1,0,1,0};
int org[maxn][maxn], jge[maxn][maxn], ans[maxn][maxn];
//origin / judge / answer
int n, m;

inline int find(int x, int y){
    int res = org[x][y];
    for(int i = 0;i < 5; ++i){
        int nx = x + dx[i],ny = y + dy[i];
        if(nx >= 0 && nx < m && ny >= 0 && ny < n){
            res += jge[nx][ny];
        }
    }
    return (res&1);
}

inline int js(){
    for(int i = 1;i < m; ++i){
        for(int j = 0;j < n; ++j){
            if(find(i-1, j)){
                jge[i][j] = 1;
            }
        }
    }
    for(int i = 0;i < n; ++ i){
        if(find(m-1,i))
            return -1;
    }
    int rs = 0;
    for(int i = 0;i < m; ++i){
        for(int j = 0;j < n; ++j){
            rs += jge[i][j];
        }
    }
    return rs;
}

inline int flip(){
    int res = -1;
    for(int i = 0;i < (1<<n); ++i){
        memset(jge,0,sizeof(jge));
        for(int j = 0;j < n; ++j){
            jge[0][n-j-1] = i>>j&1;
        }
        cout << endl;
        int num = js();
        if(num >= 0 && (res < 0 || res > num)){
            res = num;
            memcpy(ans,jge,sizeof(jge));
        }
    }
    if (res < 0){
        cout << "IMPOSSIBLE" << endl;
    }
    else {
        for(int i = 0;i < m; ++i){
            cout << ans[i][0];
            for(int j = 1;j < n; ++j){
                cout << " " << ans[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}


int main(int argc, char const *argv[])
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    while(cin >> m >> n){
        memset(org,0,sizeof(org));
        for(int i = 0;i < m; ++i){
            for(int j = 0;j < n; ++j){
                cin >> org[i][j];
            }
        }
        flip();
    }
    return 0;
}