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

POJ 1681 Painter's Problem (高斯消元)

发表于: 2015-01-27   作者:u013013910   来源:转载   浏览:
摘要: 题目地址:POJ1681跟前两题几乎一模一样的。。。不多说了。高斯消元+自由元枚举。代码如下:#include #include #include #include #include #include #include #include #include usingnamespacestd; #defineLL__int64 #definepiacos(-1.0) constintmod=1e9+

题目地址:POJ 1681

跟前两题几乎一模一样的。。。不多说了。高斯消元+自由元枚举。

代码如下:

#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;
char mp[20][20];
int a[300][300], free_x[300], free_num, state[300];
int jx[]={0,0,1,-1};
int jy[]={1,-1,0,0};
int gauss(int n)
{
        int i, j, k, h, tmp, max_r;
        free_num=0;
        for(i=0,j=0;i<n&&j<n;i++,j++){
                max_r=i;
                for(k=i+1;k<n;k++){
                        if(a[k][j]>a[max_r][j]) max_r=k;
                }
                if(max_r!=i){
                        for(k=j;k<=n;k++){
                                swap(a[i][k],a[max_r][k]);
                        }
                }
                if(!a[i][j]){
                        free_x[free_num++]=j;
                        i--;
                        continue ;
                }
                for(k=i+1;k<n;k++){
                        if(a[k][j]){
                                for(h=j;h<=n;h++){
                                        a[k][h]^=a[i][h];
                                }
                        }
                }
        }
        //printf("%d\n",free_num);
        tmp=i;
        for(i=tmp;i<n;i++){
                if(a[i][n]){
                        return -1;
                }
        }
        int tot=1<<free_num;
        int ans=INF, cnt;
        for(i=0;i<tot;i++){
                cnt=0;
                for(j=0;j<free_num;j++){
                        if(i&(1<<j)){
                                state[free_x[j]]=1;
                                cnt++;
                        }
                        else state[free_x[j]]=0;
                }
                for(j=tmp-1;j>=0;j--){
                        int t=0;
                        while(a[j][t]==0) t++;
                        state[t]=a[j][n];
                        for(k=t+1;k<n;k++){
                                if(a[j][k]) state[t]^=state[k];
                        }
                        cnt+=state[t];
                }
                //printf("%d\n",cnt);
                ans=min(ans,cnt);
        }
        return ans;
}
int main()
{
        int t, n, i, j, k, ans;
        scanf("%d",&t);
        while(t--){
                scanf("%d",&n);
                for(i=0;i<n;i++){
                        scanf("%s",mp[i]);
                }
                memset(a,0,sizeof(a));
                for(i=0;i<n;i++){
                        for(j=0;j<n;j++){
                                for(k=0;k<4;k++){
                                        int x=i+jx[k];
                                        int y=j+jy[k];
                                        if(x>=0&&x<n&&y>=0&&y<n){
                                                a[n*i+j][n*x+y]=1;
                                        }
                                }
                                a[n*i+j][n*i+j]=1;
                                if(mp[i][j]=='w'){
                                        a[n*i+j][n*n]=1;
                                }
                        }
                }
                ans=gauss(n*n);
                if(ans==-1){
                        printf("inf\n");
                }
                else{
                        printf("%d\n",ans);
                }
        }
        return 0;
}


POJ 1681 Painter's Problem (高斯消元)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
【POJ 1681】 Painter's Problem (高斯消元) Painter's Problem Time Limit: 1000MS Memory Limit
Painter's Problem Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 5075 Accepted: 2
Painter's Problem Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 3462 Accepted: 1
Painter's Problem Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u Submit
EXTENDED LIGHTS OUT Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8353 Accepted:
Painter's Problem Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 2917 Accepted: 1
Description There is a square wall which is made of n*n small square bricks. Some bricks are
高斯消元法(理论+习题) 高斯消元主要用来解多元一次线性方程组,主要用到的线性代数的知识详见矩
[转:http://www.cnblogs.com/pegasus/archive/2011/07/31/2123195.html] 高斯消元法(Gaussian eli
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 37055 Accepted: 16125 De
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号