CF-div2-192-C

题意：

从给定的图中找出某些点，这些点能够消除同一行和同一列的“怪物”。求使得最少的点的位置。

关键：要想消除整张的图的妖怪，必须选中n个点（对于n行n列来说）！！！！！！！！！！！

做法：对于每一行来说都要被消去，则每一行都至少要有一个 ‘ . ’；另外就是如果这种方法不行，则看每一列。

如果每一列都有一个 ' . ',同样也是可行的。

#include<stdio.h>
#include<string.h>

const int maxn = 105;
char mat[ maxn ][ maxn ];
bool vis[ maxn ][ maxn ];
struct node{
	int x,y;
}ans[ maxn<<2 ];

bool judge( int n ){
	for( int i=1;i<=n;i++ ){
		for( int j=1;j<=n;j++ ){
			if( vis[i][j]==false )
				return false;
		}
	}
	return true;
}

int main(){
	int n;
	while( scanf("%d",&n)==1 ){
		for( int i=1;i<=n;i++ ){
			scanf("%s",mat[i]+1);
		}
		memset( vis,false,sizeof( vis ) );
		int cnt = 0;
		for( int i=1;i<=n;i++ ){
			int fy = -1;
			for( int j=1;j<=n;j++ ){
				if( mat[i][j]=='.' ){
					fy = j;
					break;
				}
			}
			if( fy==-1 )
				continue;
			for( int k=1;k<=n;k++ ){
				vis[ i ][ k ] = true;
				vis[ k ][ fy ] = true;
			}
			ans[cnt].x = i;
			ans[cnt].y = fy;
			cnt++;
		}//each row need one '.'
		if( judge(n)==true ){
			for( int i=0;i<cnt;i++ )
				printf("%d %d\n",ans[i].x,ans[i].y);
			continue;
		}
		cnt = 0;
		memset( vis,false,sizeof( vis ) );
		for( int i=1;i<=n;i++ ){
			int fx = -1;
			for( int j=1;j<=n;j++ ){
				if( mat[j][i]=='.' ){
					fx = j;
					break;
				}
			}
			if( fx==-1 ) 
				continue;
			for( int k=1;k<=n;k++ ){
				vis[k][i] = true;
				vis[fx][k] = true;
			}
			ans[cnt].x = fx;
			ans[cnt].y = i;
			cnt++;
		}
		if( judge(n)==true ){
			for( int i=0;i<cnt;i++ )
				printf("%d %d\n",ans[i].x,ans[i].y);
			continue;
		}
		printf("-1\n");
	}
	return 0;
}