原题链接
考察:思维
错误思路:
暴力模拟,但是步骤没有统一的规矩.
思路:
递归思想.因为需要将每个棋子放在主对角线以下.那么首先保证最后一列无\(1\),那么再交换有\(1\)的行和最后一行,这样怎么也不会换到对角线上.然后可以发现最后一行,最后一列可以去掉,再重复上面的步骤
#include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef pair<int,int> PII; const int N = 1010; int n,row[N],col[N],mp[N][N],cnt; int ans[N*100][3]; void solve(int n) { if(n==1) return; for(int i=1;i<n;i++) if(!col[i]) { //交换列 ans[++cnt][0] = 2; ans[cnt][1] = i; ans[cnt][2] = n; for(int j=1;j<=n;j++) swap(mp[j][i],mp[j][n]); swap(col[i],col[n]); break; } //获取空白列 for(int i=1;i<n;i++) if(row[i]) { //交换i与n行 ans[++cnt][0] = 1; ans[cnt][1] = i,ans[cnt][2] = n; for(int j=1;j<=n;j++) swap(mp[i][j],mp[n][j]) ; swap(row[i],row[n]); break; } for(int i=1;i<=n;i++) if(mp[n][i]) { col[i]--; } solve(n-1); } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); row[x]++,col[y]++; mp[x][y]++; } solve(n); printf("%d\n",cnt); for(int i=1;i<=cnt;i++) { for(int j=0;j<3;j++) printf("%d ",ans[i][j]); printf("\n"); } return 0; }