POJ2965高消+搜索

The Pilots Brothers' refrigerator

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 12909		Accepted: 4833		Special Judge

The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.

There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.

The task is to determine the minimum number of handle switching necessary to open the refrigerator.

The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.

The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.

-+--
----
----
-+--

6
1 1
1 3
1 4
4 1
4 3
4 4

Northeastern Europe 2004, Western Subregion

 

題解:

高斯消元入門請看POJ1222 點擊打開鏈接POJ1222

這題與之前的題目有所不同 不僅僅求最小步數 而且要輸出先後順序

實際上還是有無窮解要DFS的 所以當DFS出最少解的時候

數組X[i]裏記錄的值就是方程組的解

通過之前將二維坐標轉換為方程組的係數陣的方法 現在知道是第幾個的解

在將這個值轉化為坐標即可

 

#include <iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=230;
int a[maxn][maxn+1],x[maxn];//a 是係數矩陣和增廣矩陣，x 是最後存放的解
// a[][maxn]中存放的是方程右麵的值（bi）
int equ,var;//equ 是係數陣的行數，var 是係數矩陣的列數（變量的個數）
int free_num,ans=100000000;

int abs1(int num) //取絕對值
{
    if (num>=0) return num;
    else
        return -1*num;
}
void Debug(void)
{
    int i, j;
    for (i = 0; i < equ; i++)
    {
        for (j = 0; j < var + 1; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
//調試輸出，看消元後的矩陣值，提交時，就不用了
inline int gcd(int a, int b) //最大公約數
{
    int t;
    while (b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

inline int lcm(int a, int b) //最小公倍數
{
    return a * b / gcd(a, b);
}

int dfs(int p) //枚舉自由解，隻能取0-1，枚舉完就回帶，找到最小的
{
    if (p<=free_num-1) //深入到了主對角線元素非0 的行了
    {
        //下麵就是回帶的代碼啊
        for(int i = free_num-1; i >= 0; --i)
        {
            int tmp = a[i][var] % 2;
            for(int j = i+1; j < var; ++j) //x[i]取決於x[i+1]--x[var]啊，所以後麵的解對前麵的解有影
//響。
                if(a[i][j] != 0)
                    tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
            x[i] = (tmp/a[i][i]) % 2; //上麵的正常解
        } //回帶完成了
//計算解元素為1 的個數；
        int sum=0;
        for(int i=0; i<var; i++) sum+=x[i];
        if (ans>sum) ans=sum;
        return 0;
    }
    x[p]=0;
    dfs(p-1);
    x[p]=1;
    dfs(p-1);
}
void swap(int &a,int &b)
{
    int temp=a;    //交換 2 個數
    a=b;
    b=temp;
}
int Gauss()
{
    int k,col = 0;
//當前處理的列
    for(k = 0; k < equ && col < var; ++k,++col)
    {
        int max_r = k;
        for(int i = k+1; i < equ; ++i)
            if(a[i][col] > a[max_r][col])
                max_r = i;
        if(max_r != k)
        {
            for(int i = k; i < var + 1; ++i)
                swap(a[k][i],a[max_r][i]);
        }
        if(a[k][col] == 0)
        {
            k--;
            continue;
        }
        for(int i = k+1; i < equ; ++i)
        {
            if(a[i][col] != 0)
            {
                int LCM = lcm(a[i][col],a[k][col]);
                int ta = LCM/a[i][col], tb = LCM/a[k][col];
                if(a[i][col]*a[k][col] < 0)
                    tb = -tb;
                for(int j = col; j < var + 1; ++j)
                    a[i][j] = ( (a[i][j]*ta)%2 - (a[k][j]*tb)%2 + 2 ) % 2;
                // 0 和 1 兩種狀態
            }
        }
    }
//a[i][j]隻有

//上述代碼是消元的過程，行消元完成
//解下來 2 行，判斷是否無解
//注意 K 的值，k 代表係數矩陣值都為 0 的那些行的第 1 行
    for(int i = k; i < equ; ++i)
        if(a[i][col] != 0)
            return -1;
//Debug();

//唯一解或者無窮解,k<=var
//var-k==0 唯一解；var-k>0 無窮多解，自由解的個數=var-k
//能執行到這，說明肯定有解了，無非是 1 個和無窮解的問題。
//下麵這幾行很重要，保證秩內每行主元非 0，且按對角線順序排列，就是檢查列
    for(int i = 0; i <equ; ++i)//每一行主元素化為非零
        if(!a[i][i])
        {
            int j;
            for(j = i+1; j<var; ++j)
                if(a[i][j])
                    break;
            if(j == var)
                break;
            for(int k = 0; k < equ; ++k)
                swap(a[k][i],a[k][j]);
        }
// ----處理保證對角線主元非 0 且順序，檢查列完成

    free_num=k;
    if (var-k>0)
    {
        dfs(var-1);
        return ans;
        //無窮多解，先枚舉解，然後用下麵的回帶代碼進行回帶；
//這裏省略了下麵的回帶的代碼；不管唯一解和無窮解都可以回帶，隻不過無窮解
//回帶時，默認為最後幾個自由變元=0 而已。
    }
    if(var-k<0)
        return -1;
// 無解返回 -1
    if (var-k==0)//唯一解時
    {
//下麵是回帶求解代碼，當無窮多解時，最後幾行為 0 的解默認為 0；
        for(int i = k-1; i >= 0; --i) //從消完元矩陣的主對角線非 0 的最後 1 行，開始往
//回帶
        {
            int tmp = a[i][var] % 2;

            for(int j = i+1; j < var; ++j) //x[i]取決於 x[i+1]--x[var]啊，所以後麵的解對前麵的解有影響。
                if(a[i][j] != 0)
                    tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
            //if (a[i][i]==0) x[i]=tmp;//最後的空行時，即無窮解得
            //else
            x[i] = (tmp/a[i][i]) % 2; //上麵的正常解
        }
        int sum=0;
        for(int i=0; i<var; i++)
            sum+=x[i];
        return sum;

        //回帶結束了
    }
}



int main()
{
    char map[6];
    equ=var=16;
    while(cin>>map)
    {
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        for(int i=0; i<4; i++)
        {
            if(i)
                cin>>map;
            for(int j=0; j<4; j++)
            {
                int k=i*4+j;
                a[k][k]=1;
                for(int a1=0; a1<4; a1++)
                    for(int b1=0; b1<4; b1++)
                        if(a1==i||b1==j)
                            a[k][a1*4+b1]=1;
                if(map[j]=='+')
                    a[k][16]=1;

            }
        }
        int j1=Gauss();
        cout<<j1<<endl;
        for(int i=0; i<16; i++)
            if(x[i])
                cout<<i/4+1<<' '<<i%4+1<<endl;
    }
    return 0;
}