题干：
Leo has a grid with N × N cells. He wants to paint each cell with a specific color (either black or white).
Leo has a magical brush which can paint any row with black color, or any column with white color. Each time he uses the brush, the previous color of cells will be covered by the new color. Since the magic of the brush is limited, each row and each column can only be painted at most once. The cells were painted in some other color (neither black nor white) initially.
Please write a program to find out the way to paint the grid.
Input
There are multiple test cases. The first line of input contains an integer Tindicating the number of test cases. For each test case:
The first line contains an integer N (1 <= N <= 500). Then N lines follow. Each line contains a string with N characters. Each character is either 'X' (black) or 'O' (white) indicates the color of the cells should be painted to, after Leo finished his painting.
Output
For each test case, output "No solution" if it is impossible to find a way to paint the grid.
Otherwise, output the solution with minimum number of painting operations. Each operation is either "R#" (paint in a row) or "C#" (paint in a column), "#" is the index (1-based) of the row/column. Use exactly one space to separate each operation.
Among all possible solutions, you should choose the lexicographically smallest one. A solution X is lexicographically smaller than Y if there exists an integer k, the first k - 1 operations of X and Y are the same. The k-th operation of X is smaller than the k-th in Y. The operation in a column is always smaller than the operation in a row. If two operations have the same type, the one with smaller index of row/column is the lexicographically smaller one.
Sample Input
2
2
XX
OX
2
XO
OX
Sample Output
R2 C1 R1
No solution 题目大意：
对一个空白的矩阵进行两种操作：可以将一行涂黑，将一列涂白，每一行每一列只能涂一次，给最终的图案，要求用最少次数涂出要求的图案并输出步骤。如果有多种可能性满足，那就输出字典序最小解。定义字典序：前k-1个操作相同的话，比较第k个。列比行的优先级高，其次是行（列）号小的优先级高。
解题报告：
首先需要证明的是行列之间的约束是唯一的。也就是不存在先某一行再某一列 或者 先某一列再某一行 同时成立的情况。猜出结论，然后尝试证明。对于每一个格子拆成n行，n列，这是一个二分图，对于每一个格子，相当于是一个约束，如果这个格子的最终值是X，说明列比行优先，反之说明行比列优先。假设A比B优先，那么我们就A->B连一条边。所以我们有n^2个约束关系。也就是说对于那个二分图，任意行列之间都有一个连线，那么他是个完全二分图，所以如果存在先行后列和先列后行都可以的情况，那么对于选中的那一行和那一列的那个交点来说，就是先行在列或者先列在行都可以。这就产生了矛盾，因为这显然是不符合我们刚刚构造的那个二分图的，因为刚开始是个空白图，也就是说如果这个格子所在的行列都在答案内，那么顺序是根据这个点的值是X还是O早就被确定了的，所以不可能有先行再列或者先列行都存在的情况这是不可能的。
所以我们拓扑排序的时候只需要维护那个下标之间的大小关系就可以了，对于行列之间的关系我们完全不需要管，因为完全不会存在这里的矛盾。这就大大简化了问题。
再其次就是那个vis数组的含义了，这一点也不难理解，因为我们要求的是字典序最小，所以没必要的操作我们肯定是希望做的越少越好，所以用vis来判断对这一行（列）的约束有几条了，如果约束很多，比如对某一行的约束到达了n条，说明我画不画这一行其实都差不了多少，因为最后这一行都要被覆盖成列的颜色（也就是都是O）那么我还要涂这一行干啥呢？
所以有这一个操作来减少没必要的操作，符合题意。有的时候题目给了很多限制但是其实都用不到，因为题目虽然没有说输出任意解，但是有的时候约束还是很少的，有的时候他只是这样迷惑你而已。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
char s[MAX];
int vis[MAX],in[MAX],n;
vector<int> vv[MAX],ans;//1~n代表行 n+1~2*n代表列。
bool topu() {
int tot = 0;
ans.clear();
priority_queue<int,vector<int> , greater<int> > pq;
for(int i = 1; i<=2*n; i++) {
if(in[i] == 0) pq.push(i);
}
while(pq.size()) {
int cur = pq.top();pq.pop();
tot++;
if(vis[cur] != n) ans.pb(cur);
int up = vv[cur].size();
for(int i = 0; i<up; i++) {
int v = vv[cur][i];
in[v]--;
if(in[v] == 0) pq.push(v);
}
}
if(tot<2*n) return 0;
else return 1;
}
int main()
{
int t;
cin>>t;
while(t--) {
scanf("%d",&n);
for(int i = 1; i<=2*n; i++) vv[i].clear(),vis[i]=0,in[i]=0;
for(int i = 1; i<=n; i++) {
scanf("%s",s+1);
for(int j = 1; j<=n; j++) {
if(s[j] == 'X') vv[n+j].pb(i),vis[n+j]++,in[i]++;
else vv[i].pb(n+j),vis[i]++,in[n+j]++;
}
}
bool flag = topu();
if(flag == 0) {
puts("No solution");continue;
}
int up = ans.size();
for(int i = 0; i<up; i++) {
if(ans[i]>n) printf("C%d%c",ans[i]-n,i == up-1?'\n':' ');
else printf("R%d%c",ans[i],i == up-1?'\n':' ');
}
}
return 0 ;
}
京公网安备 11010502036488号