C. Purification
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are an adventurer currently journeying inside an evil temple. After defeating a couple of weak zombies, you arrived at a square room consisting of tiles forming an n × n grid. The rows are numbered 1 through n from top to bottom, and the columns are numbered1 through n from left to right. At the far side of the room lies a door locked with evil magical forces. The following inscriptions are written on the door:
The cleaning of all evil will awaken the door!
Being a very senior adventurer, you immediately realize what this means. You notice that every single cell in the grid are initially evil. You should purify all of these cells.
The only method of tile purification known to you is by casting the "Purification" spell. You cast this spell on a single tile — then, all cells that are located in the same row and all cells that are located in the same column as the selected tile become purified (including the selected tile)! It is allowed to purify a cell more than once.
You would like to purify all n × n cells while minimizing the number of times you cast the "Purification" spell. This sounds very easy, but you just noticed that some tiles are particularly more evil than the other tiles. You cannot cast the "Purification" spell on those particularly more evil tiles, not even after they have been purified. They can still be purified if a cell sharing the same row or the same column gets selected by the "Purification" spell.
Please find some way to purify all the cells with the minimum number of spells cast. Print -1 if there is no such way.
Input
The first line will contain a single integer n (1 ≤ n ≤ 100). Then, n lines follows, each contains n characters. The j-th character in the i-th row represents the cell located at row i and column j. It will be the character 'E' if it is a particularly more evil cell, and '.' otherwise.
Output
If there exists no way to purify all the cells, output -1. Otherwise, if your solution casts x "Purification" spells (where x is the minimum possible number of spells), output x lines. Each line should consist of two integers denoting the row and column numbers of the cell on which you should cast the "Purification" spell.
Sample test(s)
input
3
.E.
E.E
.E.
output
1 1
2 2
3 3
input
3
EEE
E..
E.E
output
-1
input
5
EE.EE
E.EE.
E...E
.EE.E
EE.EE
output
3 3
1 3
2 2
4 4
5 3Note
The first example is illustrated as follows. Purple tiles are evil tiles that have not yet been purified. Red tile is the tile on which "Purification" is cast. Yellow tiles are the tiles being purified as a result of the current "Purification" spell. Green tiles are tiles that have been purified previously.
In the second example, it is impossible to purify the cell located at row 1 and column 1.
For the third example:
題解：
題目就別看它描述了，直接看下面的樣例解釋就好了。 就是E是不能放清除點的地方。
題解：
跟330A那題比較類似，如果你要清除一個n*n的正方形，你知道只用放n個點就能清除所有的方塊。
如
*****
.....
.....
.....
.....
*的就是清除他們的點。同理豎著的，橫著的，斜著的。所以我們只用構造出這樣的5個點就可以了。 所以題目轉換成判斷是否存在這樣的n個點，以及如何放的問題。
第一類：
EEEEE
E....
E....
E....
E....
這是無解的情況，因為（1，1）這個點無法清除。所以判斷無解的情況只要檢索是否存在一行都是E並且一列都是E這種就OK了。
第2類：
EEEEE
E....
E.E..
E..E.
.....
像這種，橫著存在全是E情況的，只用在每豎行找到一個能放置的點就可以了（一定存在的，不然就是上面所說的無解情況了）。
第3類：
EEEE.
E....
E.E..
E.E..
E....
這種類似於第2類分析。每個橫行找到一個能放置的點就可以了（一定存在的，不然就是上面所說的無解情況了）。
如果是 第4類這樣的
EEEE.
E....
E....
E....
.....
可以直接用第2類的構造方法來做。所以這樣就成了水題一道了。
/*
* @author ipqhjjybj
* @date 20130720
*
*/
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define clr(x,k) memset(x,k,sizeof(x))
int col[200];//列
int row[200];//行
char s[105][105];
int r,c;
int main(){
//freopen("330C.in","r",stdin);
int n;
scanf("%d",&n);
r=c=0;
getchar();
for(int i=1;i <= n;i++)
gets(s[i]+1);
for(int i=1;i<=n;i++)
for(int j = 1;j<=n;j++){
if(s[i][j]=='E'){
row[i]++,col[j]++;
if(row[i]==n) r=1;
if(col[j]==n) c=1;
if(r&&c){
puts("-1");
return 0;
}
}
}
if(r)
for(int j=1;j<=n;j++){
for(int i = 1;i<=n;i++){
if(s[i][j]=='.'){
printf("%d %d\n",i,j);
break;
}
}
}
else{
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
if(s[i][j]=='.'){
printf("%d %d\n",i,j);
break;
}
}
return 0;
}
