问题描述

2017-10-01 12-32-45 创建的截图.png 2017-10-01 12-32-54 创建的截图.png 2017-10-01 12-33-17 创建的截图.png

输入

2017-10-01 12-33-20 创建的截图.png

输出

2017-10-01 12-33-23 创建的截图.png

样例

2017-10-01 12-33-26 创建的截图.png

解题分析

2017-10-01 12-34-12 创建的截图.png 2017-10-01 12-34-14 创建的截图.png 2017-10-01 12-34-16 创建的截图.png 2017-10-01 12-34-19 创建的截图.png

有没有状态数更少的做法?

2017-10-01 12-34-21 创建的截图.png

具体实现

2017-10-01 12-34-29 创建的截图.png 2017-10-01 12-34-34 创建的截图.png

实现方案

2017-10-01 12-34-43 创建的截图.png 2017-10-01 12-34-46 创建的截图.png

程序实现

按行枚举

#include<iostream>
#include<ctime>
using namespace std;

int press[6][8];
int puzzle[6][8];

bool guess()
    {
    int r,c;
    for(r=1; r<5; r++)
        for(c=1; c<7; c++)
            //根据press第1行和puzzle数组
            //计算press其他行的值
            press[r+1][c]=(puzzle[r][c]+press[r][c-1]+press[r][c]+press[r][c+1]+press[r-1][c])%2;
    for(c=1; c<7; c++)
        //判断所计算的press数组能否熄灭第5行的所有灯
        if((press[5][c-1]+press[5][c]+press[5][c+1]+press[4][c])%2!=puzzle[5][c])
            return false;
    return true;
    }

void enumerate()
    {
    int i;
    for(i=1; i<7; i++)
        press[1][i]=0;
    while(!guess()) {
        //对press第1行的元素press[1][1]~press[1][6]的各种取值情况进行枚举
        //依次考虑
        press[1][1]++;
        i=1;
        while(press[1][i]>1) {
                press[1][i]%=2;
                i++;
                press[1][i]++;
                }
        }
    return;
    }


int main()
    {
    clock_t start,finish;
    int i,j;
    for(i=0; i<8; i++)
        press[0][i]=0;
    for(i=1; i<6; i++) {
            press[i][0]=0;
            press[i][7]=0;
            }
    int n;
    cin>>n;
    for(int c=1; c<=n; c++) {
            for(i=1; i<6; i++)
                for(j=1; j<7; j++)
                    cin>>puzzle[i][j];
            start=clock();
            enumerate();
            finish=clock();
            cout<<"time needed: "<<finish-start<<"s"<<endl;
            cout<<"PUZZLE #"<<c<<endl;
            for(i=1; i<6; i++) {
                    for(j=1; j<7; j++)
                        cout<<press[i][j]<<" ";
                    cout<<endl;
                    }
            cout<<endl;
            }
    return 0;
    }

按列枚举

#include<iostream>
#include<ctime>
using namespace std;

int press[7][7];
int puzzle[7][7];

bool guess()
    {
    int r,c;
    for(c=1; c<6; c++)
        for(r=1; r<6; r++)
            press[r][c+1]=(puzzle[r][c]+press[r-1][c]+press[r][c]+press[r+1][c]+press[r][c-1])%2;
    for(r=1; r<6; r++)
        if((press[r-1][6]+press[r][6]+press[r+1][6]+press[r][5])%2!=puzzle[r][6])
            return false;
    return true;
    }

void enumerate()
    {
    int i;
    for(i=1; i<6; i++)
        press[i][1]=0;
    while(!guess()) {
            press[1][1]++;
            i=1;
            while(press[i][1]>1) {
                    press[i][1]%=2;
                    i++;
                    press[i][1]++;
                    }
            }
    return;
    }


int main()
    {
    clock_t start,finish;
    int i,j;
    for(i=0; i<7; i++)
        press[i][0]=0;
    for(i=1; i<7; i++) {
            press[0][i]=0;
            press[6][i]=0;
            }
    int n;
    cin>>n;
    for(int c=1; c<=n; c++) {
            for(i=1; i<6; i++)
                for(j=1; j<7; j++)
                    cin>>puzzle[i][j];

            start=clock();
            enumerate();
            finish=clock();
            cout<<"time needed: "<<finish-start<<"s"<<endl;
            cout<<"PUZZLE #"<<c<<endl;
            for(i=1; i<6; i++) {
                    for(j=1; j<7; j++)
                        cout<<press[i][j]<<" ";
                    cout<<endl;
                    }
            cout<<endl;
            }
    return 0;
    }

运行结果

按行

按列

2017-10-01 20-51-16 创建的截图.png

总结

2017-10-01 20-40-16 创建的截图.png