程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1681 Painter&#39;s Problem(高斯消元)

poj 1681 Painter&#39;s Problem(高斯消元)

編輯：C++入門知識

求最少經過的步數使得輸入的矩陣全變為y。

思路：高斯消元求出自由變元，然後枚舉自由變元，求出最優值。

注意根據自由變元求其他解及求最優值的方法。

#include 
#include 
#include 
#include
#include 
#include 
#include 
#define LL long long
#define _LL __int64

using namespace std;
const int INF = 0x3f3f3f3f;

char mapp[17][17];
int a[16*16][16*16];
int equ,var;
int x[16*16];
int free_x[16*16]; //保存自由變元，枚舉求最優解
int free_num;

void init()
{
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
}

void debug()
{
    for(int i = 0; i < equ; i++)
    {
        for(int j = 0; j < var+1; j++)
            printf(%d,a[i][j]);
        printf(
);
    }
}

int Gauss()
{
	int row,col,i,j;
	int max_r;

	row = col = 0;
	free_num = 0;
	while(row < equ && col < var)
	{
		max_r = row;
		for(i = row+1; i < equ; i++)
		{
			if( abs(a[i][col]) > abs(a[max_r][col]) )
				max_r = i;
		}

		if(max_r != row)
		{
			for(j = col; j < var+1; j++)
				swap(a[max_r][j],a[row][j]);
		}
		if(a[row][col] == 0)
		{
			free_x[ free_num++ ] = col; //該列對應的變量是自由元
			col++;
			continue;
		}

		for(i = row+1; i < equ; i++)
		{
			if(a[i][col] == 0) continue;
			for(j = col; j < var+1; j++)
				a[i][j] ^= a[row][j];
		}
		row++;
		col++;
	}

	for(i = row; i < equ; i++)
		if(a[i][col] != 0)
			return -1; //無解

	if(row < var)
		return var-row; //返回自由變元的數目

	for(i = var-1; i >= 0; i--) //有唯一解
	{
		x[i] = a[i][var];
		for(j = i+1; j < var; j++)
			x[i] ^= (a[i][j] && x[j]);
	}
	return 0;
}

void solve()
{
	int t = Gauss();
	if(t == -1)
	{
		printf(inf
);
		return;
	}
	else if(t == 0)
	{
		int ans = 0;
		for(int i = 0; i < var; i++)
			ans += x[i];
		printf(%d
,ans);
		return;
	}
	else
	{
		int ans = INF;
		int sta = (1<= 0; j--)
			{
				int l,k;

				for(k = j; k < var; k++)
					if(a[j][k])
						break; //先找到該行第一個不為0的數
				x[k] = a[j][var];

				for(l = k+1; l < var; l++)
					x[k] ^= (x[l] && a[j][l]);
				cnt += x[k];
			}

			ans = min(ans,cnt);
		}
		printf(%d
,ans);
		return;
	}
}

int main()
{
    int n,test;

    scanf(%d,&test);
    while(test--)
    {
        init();
        scanf(%d,&n);

        equ = var = n*n;

        for(int i = 0; i < n; i++)
            scanf(%s,mapp[i]);

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(mapp[i][j] == 'w')
					a[i*n+j][var] = 1;
                else a[i*n+j][var] = 0;
            }
        }
		for(int i = 0; i < equ; i++)
		{
			int x = i/n;
			int y = i%n;

			for(int j = 0; j < var; j++)
			{
				int xx = j/n;
				int yy = j%n;
				if( abs(x-xx) + abs(y-yy) <= 1)
					a[i][j] = 1;
				else a[i][j] = 0;
			}
		}
		solve();
    }
    return 0;
}