即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

poj 1222 poj 1830高斯消元解决开关相关疑难问题

编程语言 winycg 12℃ 0评论




        In an extended version of the game Lights Out, is a puzzle with 5 rows of 6 buttons each (the actual puzzle has 5 rows of 5 buttons each). Each button has a light. When a button is pressed,
that button and each of its (up to four) neighbors above, below, right and left, has the state of its light reversed. (If on, the light is turned off; if off, the light is turned on.) Buttons in the corners change the state of 3 buttons; buttons on an edge
change the state of 4 buttons and other buttons change the state of 5. For example, if the buttons marked X on the left below were to be pressed,the display would change to the image on the right.







The aim of the game is, starting from any initial set of lights on in the display, to press buttons to get the display to a state where all lights are off. When adjacent buttons are pressed, the action of one button can undo the effect of another. For instance,
in the display below, pressing buttons marked X in the left display results in the right display.Note that the buttons in row 2 column 3 and row 2 column 5 both change the state of the button in row 2 column 4,so that, in the end, its state is unchanged.







Note:


1. It does not matter what order the buttons are pressed.


2. If a button is pressed a second time, it exactly cancels the effect of the first press, so no button ever need be pressed more than once.


3. As illustrated in the second diagram, all the lights in the first row may be turned off, by pressing the corresponding buttons in the second row. By repeating this process in each row, all the lights in the first


four rows may be turned out. Similarly, by pressing buttons in columns 2, 3 ?, all lights in the first 5 columns may be turned off.


Write a program to solve the puzzle.
Input
The first line of the input is a positive integer n which is the number of puzzles that follow. Each puzzle will be five lines, each of which has six 0 or 1 separated by one or more spaces. A 0 indicates
that the light is off, while a 1 indicates that the light is on initially.
Output
For each puzzle, the output consists of a line with the string: “PUZZLE #m”, where m is the index of the puzzle in the input file. Following that line, is a puzzle-like display (in the same format as
the input) . In this case, 1’s indicate buttons that must be pressed to solve the puzzle, while 0 indicate buttons, which are not pressed. There should be exactly one space between each 0 or 1 in the output puzzle-like display.
Sample Input
2
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
0 0 1 0 1 0
1 0 1 0 1 1
0 0 1 0 1 1
1 0 1 1 0 0
0 1 0 1 0 0
Sample Output
PUZZLE #1
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
PUZZLE #2
1 0 0 1 1 1
1 1 0 0 0 0
0 0 0 1 0 0
1 1 0 1 0 1
1 0 1 1 0 1




高斯消元的基础问题。

题意:给出5*6灯阵的初始状态,0为关,1为开,关一个灯,上下左右的灯状态都会改变,求操作哪些灯,使得最终状态为全部关闭。

构造30*31的系数矩阵,a[0~29][i]列向量存储第i个灯改变引起的0~29个灯中哪个会改变,置为1。a[0~29][30]存储初始的状态

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXM=35;
const int MAXN=35;
int m,n;
int a[MAXN][MAXN+1];
int x[MAXN];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
int Gauss()
{
    int i,j;
    int row,col,max_r;
    //m个方程,n个变量
    for(row=0,col=0;rowa[max_r][col])
                max_r=i;
        }
        if(max_r!=row)
        {//与第row行交换
            for(j=row;j=0;i--)
    {
        int tmp=a[i][n];
        for(j=i+1;j>T;
    int kase=1;
    while(T--)
    {
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        m=30,n=30;
        for(int i=0;i<=4;i++)
            for(int j=0;j<=5;j++)
        {
            a[6*i+j][6*i+j]=1;
            for(int t=0;t<=3;t++)
            {
                int x=i+dx[t];
                int y=j+dy[t];
                if(x>=0&&x<=4&&y>=0&&y<=5)
                    a[6*x+y][6*i+j]=1;
            }
        }
        for(int i=0;i<=29;i++)
            cin>>a[i][30];
        Gauss();
        cout<<"PUZZLE #"<




POJ 1830

         有N个相同的开关,每个开关都与某些开关有着联系,每当你打开或者关闭某个开关的时候,其他的与此开关相关联的开关也会相应地发生变化,即这些相联系的开关的状态如果原来为开就变为关,如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关,最多只能进行一次开关操作。你的任务是,计算有多少种可以达到指定状态的方法。(不计开关操作的顺序)
Input
输入第一行有一个数K,表示以下有K组测试数据。



每组测试数据的格式如下:


第一行 一个数N(0 < N < 29)


第二行 N个0或者1的数,表示开始时N个开关状态。


第三行 N个0或者1的数,表示操作结束后N个开关的状态。


接下来 每行两个数I J,表示如果操作第 I 个开关,第J个开关的状态也会变化。每组数据以 0 0 结束。


Output
如果有可行方法,输出总数,否则输出“Oh,it’s impossible~!!” 不包括引号
Sample Input
2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0
Sample Output
4
Oh,it's impossible~!!
Hint
第一组数据的说明:


一共以下四种方法:


操作开关1


操作开关2


操作开关3


操作开关1、2、3 (不记顺序)         

题意:给出一排灯的初始状态和末状态,一些开关的作用域,求操作哪些开关可以由初状态变为末状态。

对于初末状态,只需要考虑两者是否相同即可,相同的置1,不相同的置0,这样就可以转化为初始状态为全0,末状态中与初状态相同的位置为0,不相同的为0.

2^自由变元的个数=种数

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int MAXM=35;
const int MAXN=35;
int m,n;
int a[MAXN][MAXN+1];
int x[MAXN];
int t1[MAXM];
int t2[MAXM];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
int Gauss()
{
    int i,j;
    int row,col,max_r;
    //m个方程,n个变量
    for(row=0,col=0;rowa[max_r][col])
                max_r=i;
        }
        if(max_r!=row)
        {//与第row行交换
            for(j=row;j>T;
    int kase=1;
    while(T--)
    {
        int nn;
        cin>>nn;
        for(int i=0;i<=nn-1;i++)
            cin>>t1[i];
        memset(a,0,sizeof(a));
        for(int i=0;i<=nn-1;i++)
        {
            cin>>t2[i];
            if(t1[i]!=t2[i])
                a[i][nn]=1;
        }
        for(int i=0;i<=nn-1;i++)
            a[i][i]=1;
        int u,v;
        while(cin>>u>>v)
        {
            if(u==0&&v==0)
                break;
            a[v-1][u-1]=1;
        }
        n=m=nn;
        int flag=Gauss();
        if(flag==-1)
            cout<<"Oh,it's impossible~!!"<





转载请注明:CodingBlog » poj 1222 poj 1830高斯消元解决开关相关疑难问题

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情