当前位置:首页 > 资讯 > info5 > 正文

POJ 1753 Flip Game (高斯消元)

发表于: 2015-01-27   作者:u013013910   来源:转载   浏览:
摘要: 题目地址:POJ1753第三次做这道题了。第一次是刚学搜索的时候做的,第二次是刚学状态压缩枚举的时候做的,这次是刚学高斯消元、、每次都做得很艰辛。。目测这题应该没了别的方法了吧。。。。。。这题除了高斯消元外还需要枚举变元,方法是状态压缩枚举,然后返回去迭代解方程。代码如下:#include #include #include #include #include #include #include

题目地址:POJ 1753

第三次做这道题了。第一次是刚学搜索的时候做的,第二次是刚学状态压缩枚举的时候做的,这次是刚学高斯消元、、每次都做得很艰辛。。目测这题应该没了别的方法了吧。。。。。。

这题除了高斯消元外还需要枚举变元,方法是状态压缩枚举,然后返回去迭代解方程。

代码如下:

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-6;
int mp[5][5], a[20][20], free_num, free_x[20], x[20];
int jx[]={0,0,1,-1};
int jy[]={1,-1,0,0};
int gauss()
{
        int i, j, k, free_num=0, h, tmp, t;
        for(i=0,j=0;i<16&&j<16;i++,j++){
                if(a[i][j]==0){
                        for(k=i+1;k<16;k++){
                                if(a[k][j]) break;
                        }
                        if(k==16){
                                free_x[free_num++]=j;
                                i--;
                                continue ;
                        }
                        for(h=j;h<17;h++){
                                swap(a[i][h],a[k][h]);
                        }
                }
                for(k=i+1;k<16;k++){
                        if(a[k][j]){
                                for(h=j;h<17;h++){
                                        a[k][h]^=a[i][h];
                                }
                        }
                }
        }
        tmp=i;
        for(j=i;j<16;j++){
                if(a[j][16]) return INF;
        }
        int ans=INF;
        int tot=1<<free_num;
        //printf("%d\n",free_num);
        for(i=0;i<tot;i++){
                int cnt=0;
                for(j=0;j<free_num;j++){
                        if(i&(1<<j)){
                                x[free_x[j]]=1;
                                cnt++;
                        }
                        else{
                                x[free_x[j]]=0;
                        }
                }
                //printf("%d\n",cnt);
                for(j=tmp-1;j>=0;j--){
                        t=0;
                        while(a[j][t]==0) t++;
                        x[t]=a[j][16];
                        for(k=t+1;k<16;k++){
                                if(a[j][k])  x[t]^=x[k];
                        }
                        cnt+=x[t];
                }
                //printf("%d\n",cnt);
                ans=min(ans,cnt);
        }
        return ans;
}
void init()
{
        memset(a,0,sizeof(a));
        for(int i=0;i<4;i++){
                for(int j=0;j<4;j++){
                        for(int k=0;k<4;k++){
                                int x=i+jx[k];
                                int y=j+jy[k];
                                if(x>=0&&x<4&&y>=0&&y<4){
                                        a[4*i+j][4*x+y]=1;
                                }
                        }
                        a[4*i+j][4*i+j]=1;
                }
        }
}
int main()
{
        char s[6];
        int i, j, k, x, y, ans1, ans2;
        for(i=0;i<4;i++){
                scanf("%s",s);
                for(j=0;j<4;j++){
                        if(s[j]=='b') mp[i][j]=0;
                        else mp[i][j]=1;
                }
        }
        init();
        for(i=0;i<4;i++){
                for(j=0;j<4;j++){
                        a[4*i+j][4*4]=mp[i][j];
                }
        }
        ans1=gauss();
        init();
        for(i=0;i<4;i++){
                for(j=0;j<4;j++){
                        a[4*i+j][4*4]=1-mp[i][j];
                }
        }
        ans2=gauss();
        if(ans1==INF&&ans2==INF){
                printf("Impossible\n");
        }
        else{
                printf("%d\n",min(ans1,ans2));
        }
        return 0;
}


POJ 1753 Flip Game (高斯消元)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 35432 Accepted: 15487 De
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 20199 Accepted: 8752 Des
http://poj.org/problem?id=1753 题意:4*4的黑白棋子,给定棋子现在的状态怎样翻棋使棋子变成全黑o
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 33643 Accepted: 14693 De
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 26252 Accepted: 11333 De
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 38720 Accepted: 16818 De
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 31424 Accepted: 13656 De
好久没发题解了,先发一道水题题解。 这个题跟poj3279类似,比那个简单一些,棋盘大小只有4*4,但是
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 26492 Accepted: 11422 De
问题描述 Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号