POJ 2941 - Homogeneous Squares

http://poj.org/problem?id=2941

概要

n x n のボードが与えられ，各マスに数字が割り当てられている． x1 != x2 && y1 != y2 のとき，ポジション (x1, y1) と (x2, y2) は independent である，と呼ぶ． n 個のうち任意の2つのポジションが independent のとき，その n 個のポジションは n independent と呼ぶ． したがって n independent な n 個のポジションの選び方は n! 通りある．

n independent なマスに書かれている数値の合計がその選び方にかかわらず一致するとき，そのボードを homogeneous と呼ぶ． 与えられたボードが homogeneous かどうか判定する問題．

制約

解法

(i, j) の数値を a[i][j] とすると，任意の i, j について

a[i][j] + a[i+1][j+1] == a[i][j+1] + a[i+1][j]

となっていればいい．

もしこの等式が成り立たないと，左辺のケースでも右辺のケースでも残りのマスを全く同じように選ぶことができるので，最終的な合計も一致しなくなってしまう．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int N;
 7   while (scanf("%d", &N) != EOF && N != 0) {
 8     static int a[1000][1000];
 9     for (int i = 0; i < N; i++) {
10       for (int j = 0; j < N; j++) {
11         scanf("%d", &a[i][j]);
12       }
13     }
14 
15     for (int i = 1; i < N; i++) {
16       for (int j = 1; j < N; j++) {
17         if (a[i-1][j-1] + a[i][j] != a[i-1][j] + a[i][j-1]) {
18           puts("not homogeneous");
19           goto NEXT;
20         }
21       }
22     }
23     puts("homogeneous");
24 NEXT:
25     ;
26   }
27   return 0;
28 }
poj/2941.cc