Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 16216 Accepted: 6105 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 rowi 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

?

题意：

有一个4*4的正方形，每个格子上有一个符号，仅有“+”和“-”，要求将所有的符号都翻转成“-”。

规定：当翻转某个符号时，它所对应的行号和列号上符号都被翻转。

思路：

该题与POJ 1753 Flip Game类似，也有同个点翻转两次与未翻转效果相同的特点，因此只需考虑16点，每个点是否需要翻转的情况。枚举2 * （4 * 4）次即可。

但是该题压时间压得很紧，直接枚举全部它不让AC，后来马上加了个特判，就当输入时本来就全为的“-”的情况，就969MS刚好过～

?

?

?

/************************************************************************* 
    > File Name: POJ2965.cpp 
    > Author: BSlin 
    > Mail:   
    > Created Time: 2013年10月31日 星期四 15时47分23秒 
 ************************************************************************/  
  
#include   
#define INF 20  
  
int map1[5][5],map2[5][5];  
  
int min(int a, int b) {  
    return a > b ? b : a;  
}  
  
void change(int x, int y) {  
    int i, j;  
    for(i=0; i<4; i++) {  
        map2[i][y] = 1 - map2[i][y];  
    }  
    for(j=0; j<4; j++) {  
        map2[x][j] = 1 - map2[x][j];  
    }  
    map2[x][y] = 1 - map2[x][y];  
}  
  
int  check(int s) {  
    int i, j, x, y;  
    int cnt;  
    for(i=0; i<4; i++) {  
        for(j=0; j<4; j++) {  
            map2[i][j] = map1[i][j];  
        }  
    }  
    cnt = 0;  
    for(i=0; i<16; i++) {  
        if(s & (1 << i)) {  
            cnt ++;  
            x = i / 4;  
            y = i % 4;  
            change(x,y);  
        }  
    }  
    for(i=0; i<4; i++) {  
        for(j=0; j<4; j++) {  
            if(map2[i][j] != 0) {  
                return INF;  
            }  
        }  
    }  
    return cnt;  
}  
  
int main() {  
    freopen("in.txt","r",stdin);  
  
    char ch;  
    int ans, i, j, now, num;  
    bool flag;  
    flag = false;  
    for(i=0; i<4; i++) {  
        for(j=0; j<4; j++) {  
            scanf("%c",&ch);  
            if(ch == '+') {  
                map1[i][j] = 1;  
                flag = true;  
            } else if(ch == '-') {  
                map1[i][j] = 0;  
            }  
        }  
        getchar();  
    }  
    if(flag == 0) {  
        printf("0\n");  
        return 0;  
    }  
    ans = INF;  
    for(i=0; i<65536; i++) {  
        now = check(i);  
        if(ans > now) {  
            ans = now;  
            num = i;  
        }  
    }  
    printf("%d\n",ans);  
    now = 32768;  
    for(i=15; i>=0; i--) {  
        if(num >= now) {  
            num -= now;  
            printf("%d %d\n",i/4+1, i%4+1);  
        }  
        now /= 2;  
    }  
}  

?

?