POJ-2965 The Pilots Brothers' refrigerator

The Pilots Brothers’ refrigerator

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 27917 Accepted: 10810 Special Judge

Description

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.

Input

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.

Output

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.

Sample Input

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

Sample Output

6

1 1

1 3

1 4

4 1

4 3

4 4

Source

Northeastern Europe 2004, Western Subregion

飛行員兄弟的冰箱

原題連結

時間限制： 1000MS 記憶體限制： 65536K

送出總數： 27917 接受： 10810 特别法官

描述

遊戲“飛行員兄弟：跟随有條紋的大象”有玩家需要打開冰箱的任務。

冰箱門上有16個把手。每個把手可以處于以下兩種狀态之一：打開或關閉。冰箱僅在所有把手打開時才打開。把手表示為矩陣4х4。您可以在任何位置[i，j]（1≤i，j≤4）更改句柄的狀态。但是，這也會改變第i行所有句柄的狀态和第j列所有句柄的狀态。

其任務是确定打開冰箱所需的最少搖桿開關次數。

輸入

輸入包含四行。四行中的每一行都包含四個描述适當句柄初始狀态的字元。符号“+”表示搖桿處于關閉狀态，而符号“ - ”表示“打開”。至少有一個搖桿最初是關閉的。

輸出

輸入的第一行包含N - 最小切換次數。其餘的N行描述開關順序。每行包含由一個或多個空格分隔的矩陣的行号和列号。如果有幾個解決方案，你可以給他們中的任何一個。

示例輸入

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

示例輸出

6

1 1

1 3

1 4

4 1

4 3

4 4

資源

東北歐2004年，西部分區域

題解

這題和上次的POJ-1753 Flip Game一題差不多，大緻想法就是矩陣轉化成一個二進制數，那麼 0 到 217−1 2 17 − 1 之間，每個數字都是一種狀态。說白了總共就隻有這麼點狀态，是以刷 BFS 就可以了。

當然，也可以刷DFS，每個點最多會被選中一次（因為選中兩次等于沒選中），這樣一來，我們可以把選中的點看作 +，沒選中的看作 -，然後枚舉這個矩陣，最多也是 217 2 17 次就可以了。

代碼

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=(<<)+;
int L[],R[],vis[maxn],lst[maxn],q[maxn],X[maxn],Y[maxn],til,hea;
int readch()
{
    char ch=getchar();while (ch!='+'&&ch!='-')ch=getchar();return (int)(ch=='+');
}
void dfs(int stp)
{
    if (lst[stp]<) return;
    printf("%d %d\n",X[stp]+,Y[stp]+);
    dfs(lst[stp]);
}
int main()
{
    int sum=;
    for (int i=;i<;i++)
     for (int j=;j<;j++) L[i]|=<<(i<<)+j,R[j]|=<<(i<<)+j,sum|=(<<(i<<)+j)*readch();
    lst[]=-;vis[sum]=;q[til=1]=sum;
    while (til!=hea)
    {
        int x=q[++hea];
        for (int i=;i<;i++)
         for (int j=;j<;j++)
         {
             int y=x^L[i]^R[j]^<<(i<<)+j;if (vis[y]) continue;
             q[++til]=y;lst[til]=hea;X[til]=i;Y[til]=j;vis[y]=vis[x]+;
             if (!y) {printf("%d\n",vis[x]);dfs(til);return ;}
         }
    }
    return ;
}