地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5267
题意：Leo 有一个N*N 的格子，他又有一把魔法刷，这个刷子能把一行刷成黑色，一列刷成白色，每一行或每一列都只能刷一次。刚开始时，格子既不是白色，也不是黑色。
输入：题目给了刷好后的格子，其中'X'代表黑，’O’代表白。
输出：输出涂法。每一步用”R#”或”C#”表示,”#”指代数字，”R#”表示涂第’#行，”C#”表示涂第”#”列。输出时输出最小方案。最小方案是指：C<R，”#”也应该尽可能小。
思路：如果是一个有解的输入，那必然有一行或一列是同色的，即不过怎么涂，你最后一笔必然会使一行或一列同色。可以从这点出发，倒推，发现一行或一列同色时，使其还原为这一步之前的状态。
注意：因为是倒推，所以每一步都应优先取行，再取列，然后行号或列号应尽可能大，才能使之输出的序列最小。
关于还原上一步，如果用’-’表示没涂的状态，要考虑每个方格上一部的状态是’X’还是’O’,亦或是’-’;
举例说明：
输入 XX
OX
第一步：去第一行，
其中第一列有’O’,第二列没’O’,
所以可以化为：
O-
OX //R1
第二步 :去第一列，
其中第一行没’X’,第二行有’X’
所以可以化为
- -
XX //C1
第三步：去第二行，
其中第一列没’O’,第二列没’O’
所以可以化为
--
-- //R2
此时已经完成，逆序输出步骤即可
如果过程中不存在一行或一列是同色的，则可以判段此输入是非法的
/*
1500ms过的，一定还可以优化，
这次代码可能有点乱，请见谅
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std; typedef struct node{
char dir;
int order;
}node; //用于表示步骤，dir代表R或C,order代表行号或列号 const int maxn = 500+20;
bool row[maxn], column[maxn]; //记录此行是否涂过，记录此列是否涂过
char map[maxn][maxn]; //输入的格子图
int N; inline void input() //输入
{
cin>>N;
int i,j;
for(i=0;i<N;i++)
{
getchar();
for(j=0;j<N;j++)
scanf("%c",&map[i][j]);
//cin>>map[i][j];
}
memset(row,false,sizeof(row));
memset(column,false,sizeof(column)); //数组初始化
return ;
} int judge() //判断是否已经回到最初的状态
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if( map[i][j]!='-' )
return 1;
return 0;
} inline void paint()
{
stack <node> st; //存储步骤
int i,j,k;
int flag=0; //记录有没有找到一行或一列同色
node t;
//int turn=0;
while( judge())
{
flag=0;
for(i=N-1;i>=0;i--) //行'X'
{
if(row[i])
continue;
for( j=0;j<N;j++ )
if(map[i][j]!='X') //是否有一行全部为‘X’
break;
if(j==N)
{
flag=1;
break;
}
} if(flag)
{
row[i]=true;
for(j=0;j<N;j++)
{
for(k=0;k<N;k++)
if( k!=i && map[k][j]=='O' )
break;
if( k==N )
map[i][j]='-';
else
map[i][j]='O'; //还原到上一步的状态
}
t.dir='R';
t.order=i;
st.push(t);
continue;
} flag=0;
//cout<<turn<<endl;
for(i=N-1;i>=0;i--) //列'O'
{
if(column[i])
continue;
for( j=0;j<N;j++ )
if(map[j][i]!='O') //是否有一列全部为‘O’
break;
if(j==N)
{
flag=1;
break;
}
} if(flag)
{
column[i]=true;
for(j=0;j<N;j++)
{
for(k=0;k<N;k++)
if( k!=i && map[j][k]=='X' )
break;
if( k==N )
map[j][i]='-';
else
map[j][i]='X'; //还原到上一步的状态
}
t.dir='C';
t.order=i;
st.push(t);
continue;
}
else
break; //没有找到一行或一列同色,退出
} //输出
if( judge() )
cout<<"No solution\n";
else
{
t=st.top();
st.pop();
printf("%c%d",t.dir,t.order+1);
while( !st.empty() )
{
t=st.top();
st.pop();
printf(" %c%d",t.dir,t.order+1);
}
printf("\n");
}
} int main()
{
int T;
cin>>T;
while(T--)
{
input();
paint();
}
return 0;
}