Openjudge 2811 熄灯问题枚举爆搜

缺乏、安全感 2022-06-17 12:21 150阅读 0赞

熄灯问题链接如下 http://bailian.openjudge.cn/practice/2811/

该题尝试得到一组开关的状态使得灯全部被熄灭，经过分析容易得到，我们枚举第一行开关的状态后，为了达到目的，剩下所有行的开关的状态都是固定的且是由第一行开关的状态推导出来的，因为第一行开关状态固定后，可以影响第一行灯的状态的只有第二行开关的状态了，以此类推，到确定最后一行灯的状态后我们就可以验证最后得到的灯的状态是不是理想的状态了

本题有两个坑，一个是如何枚举第一行灯的状态，得到一个全排列，一种方法是最暴力的，多个for循环叠加，但是如果该行个数比较多的时候就不可行，另一种方法则是利用回溯（递归？）来生成第一行的状态，第二个坑则还是初始化的问题，切记，当我们处理完状况1，又处理状况2的时候，要把能想到的所有的初始化都做了，这里我一开始没有清空send数组导致一直出错。。。同样的错误不可以犯第三次了

代码如下

递归生成全排列版本：

#include <memory.h>
    #include<stdio.h>
    #include<iostream>
    #include<math.h>
    using namespace std;
    int button[6] ;
    int send[10][10];
    int a[10][10];
    int b[10][10];
    int dx[5] = {0,0,1,-1,0};
    int dy[5] = {1,-1,0,0,0};
    bool done;
    bool check() //检查是否全熄灭
    {
    	for (int i = 0; i < 5; i++)
    		for (int j = 0; j < 6; j++)
    			if (b[i][j] == 1) return false; //b[i][j]=1代表这个灯是点亮的
    	return true;
    }
    
    void op(int x, int y) //根据开关进行操作
    {
    	int x1, y1;
    	for (int i = 0; i < 5; i++)
    	{
    		x1 = x + dx[i]; y1 = y + dy[i];
    		if (x1 >= 0 && x1 < 5 && y1 >= 0 && y1 < 6) b[x1][y1] = !b[x1][y1];
    	}
    }
    
    void work() //找到一组第一行的状态后，进行操作
    {
    	memset(send, 0, sizeof(send));   //必须初始化send数组，否则之前开关的状态会影响到现在
    	for (int i = 0; i < 5; i++)
    		for (int j = 0; j < 6; j++)
    			b[i][j] = a[i][j];   //初始化b数组使得其与a数组相同
    
    	for (int i = 0; i < 6; i++)
    		send[0][i] = button[i];
    
    	for (int i = 0; i < 4; i++)               //对除最后一行外的灯操作
    	{
    		for (int j = 0; j < 6; j++)			 //按照搜索出来的状态，熄灯操作
    			if (send[i][j] == 1) op(i, j);   //send[i][j]==1 代表这里要按下去，即改变状态
    		for (int j = 0; j < 6; j++)				//根据当前行灯的状态，决定下一行的操作
    			if (b[i][j] == 1) send[i + 1][j] = 1;
    	}
    	for (int j = 0; j < 6; j++) if (send[4][j] == 1) op(4, j); //对最后一行进行操作
    	
    	if (check() == true)
    	{
    		done = true;
    		
    	}
    }
    
    void product_button(int x)
    {
    	if (done) return;
    	button[x] = 0;
    	if (x+1<6) product_button(x + 1);
    	else work(); //枚举出一种第一行开关状态,进行判断
    	if (done) return;
    		
    	button[x] = 1;
    	if (x+1<6) product_button(x + 1);
    	else work();  //枚举出一种第一行开关状态,进行判断
    	if (done) return;
    }
    
    void solve()
    {
    	product_button(0);
    		
    }
    
    int main()
    {
    	for (int i = 0; i < 5; i++)
    		for (int j = 0; j < 6; j++)
    			cin >> a[i][j];
    
    	done = false;
    	solve();
    
    	
    	
    	
    	
    	for (int i = 0; i < 5; i++)
    	{
    		for (int j = 0; j < 6; j++) 
    			if (j==0) cout << send[i][j];
    			else cout << " " << send[i][j];
    	    cout << endl;
    	}
    	
        return 0;
    }

程设期末上机考试有一道类似的题，还没有做出来，明天想一想

题目链接：http://cxsjsx.openjudge.cn/final2015/J/