首先如果存在解的话,只换行或换列,就可以得到解。只换行的话,每个列上主对角线上的1肯定是初始状态(没有进行任何交换)中在此列为1的行得来的,构造二分图,x代表行,y代表列, 在g[x][y]=1(也即y列上的1可有第x行得到)的两点连上一条边,进行匹配,得到每一列的1相匹配的行号(初始状态),然后构造一系列交换。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> #include <cmath> #include <stack> #include <vector> #define LL long long #define myabs(x) ((x)>0?(x):(-(x))) using namespace std; const int inf=0x3f3f3f3f; const int maxn=100+10; int g[maxn][maxn]; int leftp[maxn],vis[maxn]; int nextl[maxn],re[maxn]; int loc[maxn]; int n; int dfs(int u) { int i; for(i=1;i<=n;i++) { if(g[u][i]&&!vis[i]) { vis[i]=1; if(!leftp[i]||dfs(leftp[i])) { leftp[i]=u; return 1; } } } return 0; } int solve() { int u,v; int sum=0; for(u=1;u<=n;u++) { memset(vis,0,sizeof(vis)); if(dfs(u)) sum++; } return sum; } int main() { while(~scanf("%d",&n)) { int i,j; memset(leftp,0,sizeof(leftp)); for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&g[i][j]); int ans=solve(); if(ans<n) printf("-1\n"); else { int sum=0; for(i=1;i<=n;i++) { nextl[i]=i; loc[i]=i; } for(i=1;i<=n;i++) { re[i]=nextl[leftp[i]]; nextl[loc[i]]=nextl[leftp[i]]; loc[nextl[leftp[i]]]=loc[i]; } printf("%d\n",n); for(i=1;i<=n;i++) printf("R %d %d\n",i,re[i]); } } return 0; }