2010年第25届宁波市信息学复赛初中组题目(2)

宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 6 页 共 7 页

m列的n*m个互相之间交换了一下次序）。A教官能力尚浅，不能用大招把方阵瞬间复原。他每次操作只可以交换任意两个同学的位置。

A教官是第一次执教，他不想在上级领导面前出丑。他想让你帮他算出他至少需要多少次操作才能把方阵复原。

【输入】

输入文件lineup.in的第一行只有二个整数n和m(互相之间以一个空格分隔)。 接下来n行，每行有m对整数(a,b)。第i行的第j对整数(a,b)表示第i行的第j个同学应该排在第a行第b列。

如样例输入所示，每对整数以一对括号括起来，相邻二对整数之间有一个空格分隔，同一对的二个整数之间有一个逗号分隔。

【输出】

输出文件lineup.out中仅有一行，该行只有一个整数，代表A教官想要复原方阵最少需要的操作次数。

【样例输入】

3 3

(1,1) (2,2) (1,3) (1,2) (2,1) (2,3) (3,3) (3,2) (3,1)

【样例输出】

3

【样例说明】

被打乱的方阵为：

(1,1) (1,2) (3,3) (2,2) (2,1) (3,2) (1,3) (2,3) (3,1) 第一次操作交换第1行第2列和第2行第2列后得：

(1,1) (1,2) (2,1) (2,2) (1,3) (2,3)

? 宁波市计算机学会，2010

宁波市第 25 届中小学生计算机程序设计竞赛复赛试题（初中组）第 7 页 共 7 页 (3,3) (3,2) (3,1) 第二次操作交换第1行第2列和第2行第1列后得：

(1,1) (2,1) (3,3) (1,2) (2,2) (3,2) (1,3) (2,3) (3,1) 第三次操作交换第3行第1列和第3行第3列后得：

(1,1) (2,1) (3,1) 方阵被复原。一共进行了三次操作。

(1,2) (2,2) (3,2) (1,3) (2,3) (3,3) 【数据规模】

30%的数据中，1≤n*m≤9；

65%的数据中，1≤n*m≤20000； 1≤n≤210，1≤m≤210； 90%的数据中，1≤n≤1000，1≤m≤1000； 100%的数据中，1≤n*m≤1000000。

? 宁波市计算机学会，2010

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2010年第25届宁波市信息学复赛初中组题目(2)在线全文阅读。