Codeforces #177, Division 2, B : Polo the Penguin and Matrix

問題文

http://codeforces.com/contest/289/problem/B

概要

整数からなる 行列が与えられる。
行列の各要素に対し、値を d だけ増減する操作が許される。
行列の全ての要素を等しくするために必要な操作回数の最小値を求めよ。
不可能な場合は -1 で示せ。

解法

行列の数字を等しくする際、少なくとも一つは変化させる必要がありません。
変化しない要素を前探索で過程して、それ以外の部分について操作回数の和を求めたものの最小値が答えになります。
目標とする数字との差の MOD d の値が 0 でない要素があった場合は達成することができません。
達成できる場合、各要素と目標値との差（の絶対値）を d で除した値の和が操作回数です。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )

int check( const VVI &matrix, int d, int y, int x )
{
	const int H = matrix.size(), W = matrix[0].size();
	int target = matrix[y][x], res = 0;

	REP( i, 0, H )
	{
		REP( j, 0, W )
		{
			int mod = abs( target - matrix[i][j] );
			if ( mod % d )
			{
				return INT_MAX;
			}
			res += mod / d;
		}
	}

	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int h, w, d;
	cin >> h >> w >> d;

	VVI matrix( h, VI( w ) );
	FOR( line, matrix )
	{
		FOR( a, line )
		{
			cin >> a;
		}
	}

	int res = INT_MAX;
	REP( i, 0, h )
	{
		REP( j, 0, w )
		{
			res = min( res, check( matrix, d, i, j ) );
		}
	}

	cout << ( res == INT_MAX ? -1 : res ) << endl;

	return 0;
}