This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
行列$a$に対して，$3 \times 3$のマス目の値を全て変更出来る時，行列$a$を行列$b$に変換するには最小何回でできるか．左上から見ていく．そうすると今後どこかを変更したことでそのマスが変更されるようなことはないので，$a[i][j] \neq b[i][j]$であれば変えるしか無い．と考えれこれで言ったら通った．実装も簡単だし前のマッチの問題の方が難しいと思ったけどどうなんだろう．(考察できない場所がありそう)
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
class MatrixTransforming {
public :
int minPushes ( vector < string > a , vector < string > b ) {
int cnt = 0 ;
int n = a . size (), m = a [ 0 ]. size ();
bool flag = true ;
rep ( i , n ) {
rep ( j , m ) {
if ( a [ i ][ j ] != b [ i ][ j ]) {
if ( i + 2 < n && j + 2 < m ) {
rep ( y , 3 ) {
rep ( x , 3 ) {
if ( a [ i + y ][ j + x ] == '0' ) {
a [ i + y ][ j + x ] = '1' ;
} else {
a [ i + y ][ j + x ] = '0' ;
}
}
}
cnt ++ ;
}
if ( a [ i ][ j ] == b [ i ][ j ]) continue ;
flag = false ;
}
}
}
if ( flag ) return cnt ;
return - 1 ;
}
};