AOJ : 1117 - Missing Numbers

AOJ ACM-ICPC 実装問題

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1117


数字が書かれた表と、横一列・縦一列の数字を合計した一覧が与えられます。（詳しくは問題文の図）
また、数字が書かれた表の中には、隠された数字があり、どんな数字が当てはまるかわからない状態になっています。（？の箇所）
この問題では、この？の部分の数字を全て求めることができるかどうかを求める問題です。
もし全て求められるなら、？の数字を左上から順番に出力、求められないなら"NO"を出力します。

アルゴリズム

数字を確定させることができるのは、？が一個だけの行or列しかありません。
そのため、次のような手順でプログラムを組めば問題を解けます。

  1. ？が一つだけの列or行を探す
    • あれば、？の場所に数字を入れる
    • なければ、それ以上埋めることができないので終了し、3番へ
  2. 1番へ
  3. 全ての要素が？でなくなっているか
    • なくなっているなら、？にあてはまる数を出力
    • なくなっていないなら、"NO"を出力

プログラム

#include <stdio.h>

#define INF 999999999
#define REP(i,n,m) for(i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)

int main(void){
	int i,j;
	int h,w,tmp,startFlg,contFlg,count;
	int flg[102][102],t[102][102],totals[102],sales[102],ct[102],cs[102];

	startFlg = 1;
	while(scanf("%d",&h) && h){
		scanf("%d",&w);

		//データセット間の空行処理
		if(startFlg) startFlg = 0;
		else printf("\n");

		//配列初期化
		rep(i,h+1) totals[i] = ct[i] = 0;
		rep(i,w+1) sales[i] = cs[i] = 0;

		rep(i,h){
			rep(j,w){
				tmp = scanf("%d",&t[i][j]);

				if(tmp == 0){
					ct[i]++;
					cs[j]++;
					flg[i][j] = 1;
					t[i][j] = INF;
					getchar();
				}
				else{
					flg[i][j] = 0;
					totals[i] -= t[i][j];
					sales[j] -= t[i][j];
				}
			}

			scanf("%d",&tmp);
			totals[i] += tmp;
		}
		rep(i,w+1){
			scanf("%d",&tmp);
			sales[i] += tmp;
		}

		//？を埋められなくなるまで続行
		contFlg = 1;
		while(contFlg){
			contFlg = count = 0;
			rep(i,h) rep(j,w) if(t[i][j] == INF){
				//？が1個だけの行ならば埋められる
				if(ct[i] == 1){
					t[i][j] = totals[i];
					sales[j] -= totals[i];
					totals[i] = 0;
					ct[i] = 0;
					cs[j]--;
					contFlg = 1;
				}
				//？が1個だけの列ならば埋められる
				else if(cs[j] == 1){
					t[i][j] = sales[j];
					totals[i] -= sales[j];
					sales[j] = 0;
					ct[i]--;
					cs[j] = 0;
					contFlg = 1;
				}
				//？が複数ある場合埋められない
				else{
					count++;
				}
			}
		}

		if(count == 0){
			rep(i,h) rep(j,w) if(flg[i][j]) {
				printf("%d\n",t[i][j]);
			}
		}
		else{
			printf("NO\n");
		}
	}

	return 0;
}