poj1222

时间:2021-10-07 09:43:58

貌似又是一个矩阵图形的问题,看起来应该是不太容易,不管了先做做吧!

题目大意:
题目:灯光延伸出去(延长熄灯)??
在一个扩展的游戏版本 熄灯,它是一个难题(或者谜)在一个5行每一行有6个按钮(实际是5行每行有5个按钮/////没有扩展的游戏??),在每一个按钮上都有一个灯,当一个按钮被压下去的时候,这个灯和它四周的的(上下左右)的灯的状态将会被逆转(有木有很像昨晚做的那个反转游戏!!!不过5行6列就是2^30,不能用那个方法做了貌似),如果是开着的那么灯将被关闭,如果是关闭的那么灯将会被打开,在角落里的按钮只可以改变三个按钮的状态(邻近的按钮),在边上的按钮可以改变4个按钮的状态,其他的可以改变5个,例如下面的图像
poj1222poj1222(打X的就是准备被按得可以看到右边的有些部分变成了白色)。
这个游戏的目标是,从任何初始灯的状态开始,通过按压按钮让所有的灯都显示关闭,当按钮被按压后,邻近的按钮可以撤销他带来的影响(应该是恢复自身和刚才那个按钮的状态,应该是不会对别的按钮产生影响),例如,在下面图像的显示
poj1222
poj1222
注意:
1,不管你以什么顺序按下按钮。
2,如果第二次按下按钮,那么它会完全取消第一次按下的影像,所以没有按钮需要按两次。
3,在第二个图示中,第一行所有的等都会被关闭,在第二行按下相应的按钮,在每一行重复这个过程(如果上面是白色的,那么是不是只要在下一行对应的位置按一下就好了呢??)上面灯的状态就会转化到下一行吧
输入一个5*6的矩阵由0和1表示的,0代表灯关闭1代表开着,那么输出一个同样的矩阵也是由0和1表示0代表不按,1代表这个按钮被按过

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
题目模拟//
0 1 1 0 1 0         0 0 0 0 0 0
1 0 0 1 1 1 0 1 0 0 0 0
0 0 1 0 0 1 --> 0 0 0 0 0 0
1 0 0 1 0 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0

0 0 1 0 1 0         0 0 0 0 0 0
0 1 1 1 1 1 0 1 1 0 0 0
0 1 1 0 0 1 --> 0 0 0 0 0 0
1 0 0 1 0 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0

0 0 0 0 1 0         0 0 0 0 0 0
0 0 0 0 1 1 0 1 1 0 1 0
0 1 0 0 0 1 --> 0 0 0 0 0 0
1 0 0 1 0 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0         0 0 0 0 0 0
0 0 0 1 0 0 0 1 1 0 1 0
0 1 0 0 1 1 --> 0 0 0 1 0 0
1 0 0 1 0 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0         0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0
0 1 1 1 0 1 --> 0 0 0 1 0 0
1 0 0 0 0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0         0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0
0 0 1 1 0 1 --> 0 0 0 1 0 0
0 1 1 0 0 1 0 1 1 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0         0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0
0 0 0 1 0 1 --> 0 0 0 1 0 0
0 0 0 1 0 1 0 1 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0         0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0
0 0 0 0 0 1 --> 0 0 0 1 0 0
0 0 1 0 1 1 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0         0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0
0 0 0 0 0 0 --> 0 0 0 1 0 0
0 0 1 0 0 0 0 1 1 1 0 1
0 0 0 0 0 1 0 0 0 0 0 0

从上面的模拟过程中可以看出来这样的方式还是有点问题存在,那么就是把所有的灯都压到了最后一行,那么最后一行应该怎么解决呢?????似乎有一些行不通


/////////////////////////////////////////////////////////////////////////////////////////
实在是没有什么思路所以看了一下题解,题解貌似都是什么高斯消元,听起来很高大上,不过不明白就是了,看了另外一个题解报告说是只要枚举第一行就行,只要第一行固定了那么下面的也就固定了,听起来是很有道理的,只要第一行是固定的那么下面的就按照上面的那种方式来就行了,直到找到一组解(http://www.hankcs.com/program/algorithm/poj-1222-extended-lights-out.html)。
先按照这种理解方式做一下吧。
因为是枚举第一行,所以产生的状态也就是2^6,应该还是一个很小的数字。


测试数据确实没有问题,不过提交后无情的给了一个WA!!!
为啥呢????好吧,我也不知到为什么,不过可以测试一下数据
找到BUG搜索应该从0开始的
///////////////////////////////for(i=1; i<64; i++) 
跟上一次做题的时候错的差不多,我晕,认栽了,仔细确实不能只嘴上说说的

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std; #define maxn 10 //2^6 = 64 int dir[5][2] = {{0,0},{0,1},{1,0},{-1,0},{0,-1}};
int c[10][10]; void changeXY(int b[][10], int x, int y);//把xy坐标和四周的坐标改变
int  OK(int x, int y);//判断xy坐标是否合法
int  Find(int b[][10]);//第一行固定后,往下面查找,看看最后一行是否会变为全0 int main()
{
    int T, t=1;     scanf("%d", &T);     while(T--)
    {
        int i, j, k,a[10][10], b[10][10];         for(i=1; i<=5; i++)
        for(j=1; j<=6; j++)
            scanf("%d", &a[i][j]);         for(i=0; i<64; i++)
        {
            for(j=1; j<=5; j++)
            for(k=1; k<=6; k++)
                b[j][k] = a[j][k], c[j][k] = 0;             k = i;
            for(j=6; j>0; j--)
            {
                if(k % 2)
                {
                    changeXY(b, 1, j);
                    c[1][j] = 1;
                }
                k /= 2;
            }             if(Find(b) == 1)
                break;
        }         printf("PUZZLE #%d\n", t++);
        for(i=1; i<=5; i++)
        for(j=1; j<=6; j++)
            printf("%d%c", c[i][j], j == 6 ? '\n' : ' ');
    }     return 0;
}
void changeXY(int b[][10], int x, int y)//把xy坐标和四周的坐标改变
{
    int i, nx, ny;     for(i=0; i<5; i++)
    {
        nx = x + dir[i][0];
        ny = y + dir[i][1];         if(OK(nx, ny))b[nx][ny] = 1 - b[nx][ny];
    }
}
int  OK(int x, int y)//判断xy坐标是否合法
{
    if(x > 0 && x < 6 && y > 0 && y < 7)
        return 1;
    return 0;
}
int  Find(int b[][10])//第一行固定后,往下面查找,看看最后一行是否会变为全0
{
    int i, j;     for(i=1; i<=4; i++)
    for(j=1; j<=6; j++)
    {
        if(b[i][j])
        {
            changeXY(b, i+1, j);
            c[i+1][j] = 1;
        }
    }     for(i=1; i<=6; i++)
        if(b[5][i])return 0;
    return 1;
}

poj1222的更多相关文章

  1. 二进制枚举例题&vert;poj1222,poj3279,poj1753

    poj1222,poj3279,poj1753 听说还有 POJ1681-画家问题 POJ1166-拨钟问题 POJ1054-讨厌的青蛙

  2. POJ1222、POJ3279、POJ1753--Flip

    POJ1222-EXTENDED LIGHTS OUT POJ3279-Fliptile POJ1753-Flip Game 为什么将着三个题放一起讲呢?因为只要搞明白了其中一点,就可以一次3ac了- ...

  3. poj1222(高斯消元法解异或方程组&plus;开关问题)

    题目链接:https://vjudge.net/problem/POJ-1222 题意:给定一个5×6的01矩阵,改变一个点的状态时它上下左右包括它自己的状态都会翻转,因为翻转2次等价与没有翻转,那么 ...

  4. 高斯消元几道入门题总结POJ1222&amp&semi;&amp&semi;POJ1681&amp&semi;&amp&semi;POJ1830&amp&semi;&amp&semi;POJ2065&amp&semi;&amp&semi;POJ3185

    最近在搞高斯消元,反正这些题要么是我击败了它们,要么就是这些题把我给击败了.现在高斯消元专题部分还有很多题,先把几道很简单的入门题总结一下吧. 专题:http://acm.hust.edu.cn/vj ...

  5. poj1222 EXTENDED LIGHTS OUT 高斯消元&vert;&vert;枚举

    Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 8481   Accepted: 5479 Description In an ...

  6. poj1222 EXTENDED LIGHTS OUT

    设输入矩阵为A,输出矩阵为B,目标矩阵为C(零矩阵). 方便起见,矩阵行列下标均从1开始. 考虑A矩阵元素a(i,j),B矩阵中与其相邻的元素 b(i,j),b(i - 1, j),b(i + 1,j ...

  7. &lbrack;POJ1222&rsqb;EXTENDED LIGHTS OUT(高斯消元,异或方程组)

    题目链接:http://poj.org/problem?id=1222 题意:开关是四连通的,每按一个就会翻转自己以及附近的四个格(假如有).问需要翻转几个,使他们都变成关. 把每一个灯看作一个未知量 ...

  8. POJ1222 高斯消元法解抑或方程

    第一次学怎么用高斯消元法解抑或方程组,思想其实很简单,方法可以看下面的链接:http://blog.csdn.net/zhuichao001/article/details/5440843 有了这种思 ...

  9. &lbrack;Gauss&rsqb;POJ1222 EXTENDED LIGHTS OUT

    题意:给一个5*6的矩阵 1代表该位置的灯亮着, 0代表该位置的灯没亮 按某个位置的开关,可以同时改变 该位置 以及 该位置上方.下方.左方.右方, 共五个位置的灯的开.关(1->0, 0-&g ...

  10. bzoj2466&comma;poj1222

    都是简单的异或高斯消元 由于bzoj2466要求解得最小和,所以我们最后还要穷举*元取最优解 type node=record        po,next:longint;      end; . ...

随机推荐

  1. Mac os装软件时提示显示需要安装旧Java SE 6运行环境解决办法

    这个时Java版本的问题,换用合适的低版本即可,下面是官方的 https://support.apple.com/kb/DL1572?viewlocale=zh_CN&locale=en_US ...

  2. JS获取html对象的几种方式说明

    document.getElementById("zx"); 通过ID获取html元素对象,ID号在html文档当中应该是唯一的.返回的是唯一element对象.并且所有浏览器都兼 ...

  3. String解析

    常量池(Constant Pool):指的是在编译期被确定,并被保存在已编译的.class文件中的一些数据.JVM虚拟机为每个被装载的类型维护一个常量池.常量池就是该类型所用到常量的一个有序集和,包括 ...

  4. 九度oj 1349 数字在排序数组中出现的次数

    原题链接:http://ac.jobdu.com/problem.php?pid=1349 二分.. #include<algorithm> #include<iostream&gt ...

  5. TOGAF企业连续体和工具之企业连续体构成及架构划分

    TOGAF企业连续体和工具之企业连续体构成及架构划分 又回头看了之前文章的评论,本人也同样感慨这些文章的确像政治课本般的虚无缥缈,所以对费力看完却觉得无从下手的看官致以诚挚的歉意和理解,因为这个问题也 ...

  6. AFNetworking源码简析

    AFNetworking基本是苹果开发中网络请求库的标配,它是一个轻量级的网络库,专门针对iOS和OS X的网络应用设计,具有模块化的架构和丰富的APIs接口,功能强大并且使用简单,深受苹果应用开发人 ...

  7. html页面禁止用户右键粘贴复制保存的代码

    HTML页面禁止选择.页面禁止复制.页面禁止右键 原创古城寨主2018-03-01 17:50:59评论(1)228人阅读   HTML页面内容禁止选择.复制.右键 刚在一个看一个站点的源代码的的时候 ...

  8. &lbrack;精华&rsqb;&lbrack;推荐&rsqb;CAS SSO单点登录服务端客户端实例

    1.修改server.xml文件,如下: 注意: 这里使用的是https的认证方式,需要将这个配置放开,并做如下修改: <Connector port="8443" prot ...

  9. YAML配置,spring boot 配置文件

    1 概念YAML是一种人们可以轻松阅读的数据序列化格式,并且它非常适合对动态编程语言中使用的数据类型进行编码.YAML是YAML Ain't Markup Language简写,和GNU(" ...

  10. 分享一个 jsPDF的简单使用以及中文编码问题的解决

    后台一个下载文件中内容国际化问题的坑甩到了前端 前端自己匹配,自己处理国际化,生成文件下载 jsPDF-AutoTable    挺靠谱 中文乱码, 还是好人多啊 解决方式如下文章 jsPDF的简单使 ...