Problem 1117 : Missing Numbers

問題概要

? ? 70 105
? 50 ? 150
30 60 90 180
45 150 240 435

のように、h行w列の表および、それぞれの行・列の合計値が与えられる。
表の中にはいくつか'?'が書かれている。
合計値に合うように'?'の値を決められるならばその値を対応する'?'の出現した順に、決められないならば"NG"を出力せよ。

'?'が行・列の合計値の欄に現れることはない。

解法

Respect2Dさんの日記を参考にした。
?が一つだけの行・列を探し、'?'を一つずつ確定させて行くとよいらしい。

ソースコード

int h,w,d[100][100];
int nq,q[100][100];

int main()
{
	bool fst=1;
	while(scanf("%d",&h),h)
	{
		scanf("%d",&w); w++; h++;
		nq=0;
		rep(i,h)rep(j,w)
		{
			char in[9]; scanf("%s",in);
			if(in[0]=='?')d[i][j]=inf,q[i][j]=1,nq++;
			else d[i][j]=atoi(in),q[i][j]=0;
		}
		
		bool f=0;
		while(nq&&!f)
		{
			f=1;
			rep(i,h-1)
			{
				int p=-1,sum=0;
				rep(j,w-1)
				{
					if(d[i][j]==inf)p=p==-1?j:-2;
					else sum+=d[i][j];
				}
				if(p>=0)
				{
					d[i][p]=d[i][w-1]-sum;
					nq--; f=0; goto NEXT;
				}
			}
			rep(j,w-1)
			{
				int p=-1,sum=0;
				rep(i,h-1)
				{
					if(d[i][j]==inf)p=p==-1?i:-2;
					else sum+=d[i][j];
				}
				if(p>=0)
				{
					d[p][j]=d[h-1][j]-sum;
					nq--; f=0; goto NEXT;
				}
			}
			NEXT:;
		}
		
		if(!fst)puts(""); else fst=0;
		if(nq)puts("NO");
		else rep(i,h)rep(j,w)if(q[i][j])printf("%d\n",d[i][j]);
	}
	return 0;
}