POJ-1222-尺取法,开关灯


题目大意:有一个5*6的网格图,每个格子都是一个灯,按灯的时候会使这个灯周围其余4个灯改变状态,给出初始状态,问最后按灯的结果;

题目解析:先暴力出第一行所有按灯的情况,然后从第一行到第五行,如果i,j是亮的话,只能按i+1,j,最后判断最后一行是否全为暗的即可;

AC代码:

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 110;
int grid[maxn][maxn],ans[maxn][maxn];
int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
int n,t[maxn][maxn],c;
void push(int x,int y)
{
    t[x][y]^=1;
    for(int i=0;i<4;i++)
    {
        int u=x+dx[i];
        int v=y+dy[i];
        if(u<=0||u>5||v<1||v>6) continue;
        t[u][v]^=1;
    }
}
bool ok()
{
    memcpy(t,grid,sizeof(grid));
    for(int i=1;i<=6;i++)
    {
        if(ans[1][i])
        {
            push(1,i);
        }
    }
    for(int i=1;i<5;i++)
    {
        for(int j=1;j<=6;j++)
        {
            if(t[i][j])
            {
                ans[i+1][j]=1;
                push(i+1,j);
            }
            else
            {
                ans[i+1][j]=0;
            }
        }
    }
    for(int i=1;i<=6;i++)
    {
        if(t[5][i]==1)
            return false;
    }
    return true;
}
void solve()
{
    for(int i=0;i<(1<<6);i++)
    {
        for(int j=0;j<6;j++)
        {
            if(i&(1<