4267: Swapping Puzzle

# Swapping Puzzle ### 内存 1024MB ### 时间 2S ## 题目描述 你有两个网格$A$和$B$，每个网格有$H$行和$W$列。 对于每对整数$(i,j)$满足$1 ≤ i ≤ H$和$1 ≤ j ≤ W$，让$(i,j)$表示第$i$行第$j$列的单元格。在网格$A$中，单元格$(i,j)$包含整数$A_{i,j}$。在网格$B$中，单元格$(i,j)$包含整数$B_{i,j}$。 你可以重复以下操作任意次数，可能为零次。在每次操作中，你执行以下操作之一： - 选择一个满足$1 ≤ i ≤ H-1$的整数$i$，并交换网格$A$中第$i$行和第$(i+1)$行。 - 选择一个满足$1 ≤ i ≤ W-1$的整数$i$，并交换网格$A$中第$i$列和第$(i+1)$列。 确定是否可能通过重复上述操作使网格$A$与网格$B$相同。如果可能，请输出使网格$A$与网格$B$相同所需的最小操作次数。 这里，当且仅当对于所有满足$1 ≤ i ≤ H$和$1 ≤ j ≤ W$的整数对$(i,j)$，网格$A$中单元格$(i,j)$中写的整数等于网格$B$中单元格$(i,j)$中写的整数时，网格$A$与网格$B$相同。 ## 输入格式 输入按以下格式从标准输入给出： $H$ $W$ $A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,W}$ $A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,W}$ $\cdots$ $A_{H,1}$ $A_{H,2}$ $\cdots$ $A_{H,W}$ $B_{1,1}$ $B_{1,2}$ $\cdots$ $B_{1,W}$ $B_{2,1}$ $B_{2,2}$ $\cdots$ $B_{2,W}$ $\cdots$ $B_{H,1}$ $B_{H,2}$ $\cdots$ $B_{H,W}$ ## 输出格式 如果无法使网格$A$与网格$B$相同，输出`-1`。否则，输出使网格$A$与网格$B$相同所需的最小操作次数。 ## 输入输出样例 ### 输入样例1 ``` 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 3 2 5 4 11 13 12 15 14 6 8 7 10 9 16 18 17 20 19 ``` ### 输出样例1 ``` 3 ``` ### 输入样例2 ``` 2 2 1 1 1 1 1 1 1 1000000000 ``` ### 输出样例2 ``` -1 ``` ### 输入样例3 ``` 3 3 8 1 6 3 5 7 4 9 2 8 1 6 3 5 7 4 9 2 ``` ### 输出样例3 ``` 0 ``` ### 输入样例4 ``` 5 5 710511029 136397527 763027379 644706927 447672230 979861204 57882493 442931589 951053644 152300688 43971370 126515475 962139996 541282303 834022578 312523039 506696497 664922712 414720753 304621362 325269832 191410838 286751784 732741849 806602693 806602693 732741849 286751784 191410838 325269832 304621362 414720753 664922712 506696497 312523039 834022578 541282303 962139996 126515475 43971370 152300688 951053644 442931589 57882493 979861204 447672230 644706927 763027379 136397527 710511029 ``` ### 输出样例4 ``` 20 ``` ## 数据范围与提示 【样例1说明】 交换初始网格$A$的第四列和第五列得到以下网格： ``` 1 2 3 5 4 6 7 8 10 9 11 12 13 15 14 16 17 18 20 19 ``` 然后，交换第二行和第三行得到以下网格： ``` 1 2 3 5 4 11 12 13 15 14 6 7 8 10 9 16 17 18 20 19 ``` 最后，交换第二列和第三列得到以下网格，该网格与网格$B$相同： ``` 1 3 2 5 4 11 13 12 15 14 6 8 7 10 9 16 18 17 20 19 ``` 你可以通过上述三次操作使网格$A$与网格$B$相同，并且无法用更少的操作次数完成，所以输出3。 【样例2说明】 无法通过操作使网格$A$与网格$B$匹配，所以输出-1。 【样例3说明】 网格$A$在一开始就已经与网格$B$相同。 【数据范围】 - 所有输入值都是整数。 - $2 ≤ H, W ≤ 5$ - $1 ≤ A_{i,j}, B_{i,j} ≤ 10^9$。 ## 题目来源 ABC332D