博客

POJ1753

POJ1753是一个点灯游戏，注意每个点最多只能被点一次（多点则还原），然后难点就在如何每次从16个点中取出N个点（递归实现）。

#include<iostream>
using namespace std;
class map{
    public:
        bool s[4][4];
        map(){}
        void turn(int x, int y)
        {
            if(s[x][y])s[x][y] = false;
            else s[x][y] = true;
        }
        void flip(int x, int y)
        {
            if(x - 1 >= 0)turn(x - 1, y);
            if(x + 1 <= 3)turn(x + 1, y);
            if(y - 1 >= 0)turn(x, y - 1);
            if(y + 1 <= 3)turn(x, y + 1);
            turn(x, y);
        }
        bool finish()
        {
            int sum = 0;
            for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
            if(s[i][j])++sum;
            if(sum == 0 || sum == 16)return true;
            return false;
        }
        bool dfs(int x, int y, map m)
        {
            if(y == 0)
            {
                if(m.finish())return true;
                return false;
            }
            map ma;
            for(int i = x; i < 17 - y; i++)
            {
                ma = m;
                ma.flip(i/4, i%4);
                if(dfs(i + 1, y - 1, ma))return true;
            }
            return false;
        }
        int solve()
        {
            for(int i = 0; i <= 16; i++)
            if(dfs(0, i, *this))return i;
            return -1;
        }
        friend istream& operator>>(istream& is, map& m)
        {
            char s[4][4];
            for(int i = 0; i < 4; i++)
            cin >> s[i];
            for(int i = 0; i < 4; i++)
            for(int j = 0; j < 4; j++)
            {
                if(s[i][j] == 'b')m.s[i][j] = true;
                else m.s[i][j] = false;
            }
            return is;
        }
};
int main()
{
    map m;
    cin >> m;
    int result = m.solve();
    if(result == -1)cout << "Impossible" << endl;
    else cout << result << endl;
    return 0;
}