首页 > 代码库 > codeforces 724B Batch Sort(暴力-列交换一次每行交换一次)
codeforces 724B Batch Sort(暴力-列交换一次每行交换一次)
题目链接：http://codeforces.com/problemset/problem/724/B
题目大意：
给出N*M矩阵，对于该矩阵有两种操作：
（保证，每行输入的数是 1-m 之间的数且不重复）
1.交换两列，对于整个矩阵只能操作一次
2.每行交换两个数。
交换后是否可以使每行都是1-m 数字递增。
解题思路：
1.得到矩阵后先判断，是否每行可以交换两个数可以得到递增的矩阵，如果可以则输出“YES”.
2.暴力交换两列，交换两列后，判断每行是否可以交换两个数得到递增的矩阵，如果可以则输出“YES”.
[注意：如果交换之后不可得到递增的矩阵，要记得将交换后的两列交换回来]
AC Code:
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int N=22; 5 int na[N][N]; 6 int n,m; 7 8 int judge(int na[N][N]) 9 {10 for(int i=1; i<=n; i++)11 {12 int cut=0;13 for(int j=1; j<=m; j++)14 if(na[i][j]!=j)cut++;15 if(cut>2)return 0;16 }17 return 1;18 }19 int main()20 {21 while(scanf("%d%d",&n,&m)!=EOF)22 {23 for(int i=1; i<=n; i++)24 for(int j=1; j<=m; j++)25 scanf("%d",&na[i][j]);26 if(judge(na))27 {28 printf("YES\n");29 continue;30 }31 int flag=0;32 for(int i=1; i<=m; i++)33 {34 if(flag)break;35 for(int j=i+1; j<=m; j++)36 {37 if(flag)break;38 for(int x=1; x<=n; x++)swap(na[x][i],na[x][j]);39 if(judge(na))flag=1;40 for(int x=1; x<=n; x++)swap(na[x][i],na[x][j]);41 }42 }43 printf("%s\n",flag?"YES":"NO");44 }45 return 0;46 }
codeforces 724B Batch Sort(暴力-列交换一次每行交换一次)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。