首页 > 代码库 > POJ 1222 extended lights out 高斯消元 板子题

POJ 1222 extended lights out 高斯消元 板子题

  题目链接:http://poj.org/problem?id=1222

  题目描述:其实就是开关问题, 按下按钮会影响当前和周围的四个按钮, 问关闭所有灯的方案

  解题思路:以前用搜索做过, 那时候是刚刚接触ACM的时候, 当时劲头真足啊, 这个解释的很好:http://blog.csdn.net/u013508213/article/details/47263183

  代码:

技术分享
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100 + 10;
int a[maxn][maxn]; // 增广矩阵
int x[maxn]; // 解集
bool freeX[maxn]; // 标记是否有自由变元

//高斯消元解方程组
//返回值-2表示有浮点数解, 无整数解
//返回值-1表示无解, 0表示唯一解, 大于0表示有无穷解,返回自由变元个数
//有equ个方程, var个变元
//增广矩阵函数[0, equ-1]
//增广矩阵列数[0, var]
int gauss(int equ, int var) {
    for( int i = 0; i <= var; i++ ) {
        x[i] = 0;
        freeX[i] = true;
    }
    //转换为阶梯矩阵
    //col表示当前正在处理的这一列
    int col = 0;
    int row = 0;
    //maxR表示当前这个列中元素绝对值最大的行
    int maxRow;
    for( ; row < equ && col < var; row++, col++ ) {
        //枚举当前正在处理的行
        //找到该col列元素绝对值最大的那行与第k行交换
        maxRow = row;
        for( int i = row + 1; i < equ; i++ ) {
            if( abs(a[maxRow][col]) < abs(a[i][col])) {
                maxRow = i;
            }
        }
        if( maxRow != row ) {
            //与第row行交换
            for( int j = row; j < var + 1; j++ ) {
                swap(a[row][j], a[maxRow][j]);
            }
        }
        if( a[row][col] == 0 ) {
            row--;
            continue;
        }
        for( int i = row + 1; i < equ; i++ ) {
            //枚举要删的行
            if( a[i][col] != 0 ) {
                for( int j = col; j < var + 1; j++ ) {
                    a[i][j] ^= a[row][j];
                }
            }
        }
    }
    for( int i = var - 1; i >= 0; i-- ) {
        x[i] = a[i][var];
        for( int j = i + 1; j < var; j++ ) {
            x[i] ^= (a[i][j] && x[j]);
        }
    }
    return 0;
}
int main() {
    int ncase;
    int ca = 1;
    scanf("%d", &ncase);
    while (ncase--)
    {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < 30; i++)
        {
            scanf("%d", &a[i][30]);
        }
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 6; j++)
            {
                int t = i * 6 + j;
                a[t][t] = 1;
                if(i>0)a[(i-1)*6+j][t]=1;
                if(i<4)a[(i+1)*6+j][t]=1;
                if(j>0)a[i*6+j-1][t]=1;
                if(j<5)a[i*6+j+1][t]=1;
            }
        }
        gauss(30, 30);
        printf("PUZZLE #%d\n", ca++);
        for(int i = 0; i < 30; i++)
        {
            printf("%d", x[i]);
            if((i+1) % 6 == 0)
                printf("\n");
            else
                printf(" ");
        }
    }
    return 0;
}
View Code

  思考:需要熟知原理, 多见题, 嗯。

POJ 1222 extended lights out 高斯消元 板子题