Digital Matrix (UVa Live Archive Asia - Site 9 (Bangladesh) - 2010/2011 Dhaka (Bangladesh))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4858

問題

[1,k]の数値を使ったn*nの行列A、Bがある。Aの行列の一か所を選び[1,k]の数値に変えるという操作を繰り返してBの行列にする。ただし、数値を変化させたときに対象行列となってはいけない。最低何回数値を変化させる必要があるか？
1<=n<=100
1<=k<=9

解法

まず-1となるケースは、「AとBが一致しないがBが対象行列」と「n=2、k=2でa12=b21!=a21=b12」の2つのみ。他の場合答えは異なっている個数になるか、その数値に+1,+2した数値になる。+1になるケースはk>=3でaij=bji!=aji=bijとなっている個所が1個あり、それ以外の部分は全てaij=aji=bij=bjiとなっている場合。+2になるケースは+1となるケースでk=2の場合。
コーナーケースが多いので注意。また対象行列のチェックをするのは数値を変化させた直後と言うことに注意。