CF 329A(Purification-贪心-非DLX)

分类：贪心棋牌方块模拟 2013-07-21 14:33 103人阅读评论(0) 收藏举报

A. 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 numbered 1through 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:

这题是NOI 2013 易做图残以后做的第一次Div 1，马上就掉回蓝了轻囧

这题一开始以为DLX各种弱。。。。。

印度尼西亚的人怎么都出这种游戏题目、、、、

进入正解模式：

我们发现出现‘十‘E 是无解的

否则必然存在n次Purification（净化）的解.

反证：

假设最优解为n+1

那么必然有一行/一列净化了2次，删掉那次不影响结果

假设存在答案为n的净化方案：

因为只做了n遍，必然每行取一个(%号表示净化点)

或每列：

所以考虑这2种情况，随便取即可，反之无解

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Lson (x<<1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (1000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
int n,a[MAXN]={0},d[MAXN]={0};
bool b[MAXN][MAXN]={0};
int main()
{
//	freopen("Purification.in","r",stdin);
	cin>>n;
	For(i,n) For(j,n)
	{
		char c;
		while (cin>>c)
		{
			if (c=='.') b[i][j]=1,a[i]=j,d[j]=i;
			else if (c=='E') b[i][j]=0;
			else continue;
			break;
		}
	}
	/*
	For(i,n)
	{
		bool bo=0;
		For(j,n) if (b[i][j]) bo=1;
		if (!bo) {puts("-1");return 0;} 
		bo=0;
		For(j,n) if (b[j][i]) bo=1;
		if (!bo) {puts("-1");return 0;} 
	}*/
	//For(i,n) cout<<a[i]<<' ';cout<<endl;
	//For(i,n) cout<<d[i]<<' ';cout<<endl;
	
	bool bo=0;
	For(i,n) if (!a[i]) bo=1;
	if (!bo)
	{
		For(i,n) cout<<i<<' '<<a[i]<<endl;
		return 0;
	}
	
	bo=0;
	For(i,n) if (!d[i]) bo=1;
	if (!bo)
	{
		For(i,n) cout<<d[i]<<' '<<i<<endl;
		return 0;
	}
	
	puts("-1");
	
	
	
	return 0;
}

补充：软件开发 , C++ ,