AOJ : 2002 - X-Ray Screening System

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2002
日本語なので省略です。

アルゴリズム

X線写真の前面から、順番にどの種類の荷物が写っているかを深さ優先で試していく。
例えば、サンプルの3番目の場合、

• A->B->C->D の順番で前面から写っている
• A->B->D->C の順番で前面から写っている
• A->C->B->D の順番で前面から写っている
• ・・・

という具合で、すべてのパターンを試していきます。
もし、この探索途中で、Safe であると確信できる並びが見つかったなら、その時点で Safe と出力するようにしました。

プログラム

#include <stdio.h>

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

int h,w;
int mt[26][4]; //[i][0]:左端 [1]:右端 [2]:上端 [3]:下端
int used[26];
char t[54][54];

//(a+'A') の文字が (b+'B') の文字より前にあるかの判定
//その判定と同時に, a が長方形であるかも判定する
int isFront(int a,int b){
	int i,j;
	REP(i,mt[a][2],mt[a][3]+1){
		REP(j,mt[a][0],mt[a][1]+1){
			if(t[i][j] == b + 'A' || t[i][j] == '.'){
				return 0;
			}
		}
	}
	return 1;
}

//Safeであるかどうかの判定
int isSafe(int idx,int rem){
	int i,j;
	int okFlg;

	if(rem == 0){
		//最後の記号が長方形か判定するためにisFrontを使う
		return isFront(idx,-1);
	}

	used[idx] = 1;
	rep(i,26){
		if(mt[i][1]!=-1 && !used[i]){

			//今まで使用した記号全てより後ろにあるか判定
			okFlg = 1;
			rep(j,26) if(used[j] && !isFront(j,i)){
				okFlg = 0;
				break;
			}

			if(okFlg && isSafe(i,rem-1)) return 1;
		}
	}
	used[idx] = 0;

	return 0;
}

int main(void){
	int i,j;
	int n,idx,count;

	scanf("%d",&n);
	while(n--){
		scanf("%d%d",&h,&w);

		rep(i,26){
			mt[i][0] = w+1;
			mt[i][1] = -1;
			mt[i][2] = h+1;
			mt[i][3] = -1;
		}

		count = 0;
		rep(i,h){
			scanf("%s",t[i]);
			rep(j,w) if(t[i][j] != '.') {
				idx = t[i][j] - 'A';

				//記号の種類カウント
				if(mt[idx][1] == -1) count++;

				//記号の左端,右端,上端,下端を更新
				if(mt[idx][0] > j) mt[idx][0] = j;
				if(mt[idx][1] < j) mt[idx][1] = j;
				if(mt[idx][2] > i) mt[idx][2] = i;
				if(mt[idx][3] < i) mt[idx][3] = i;
			}
		}

		rep(i,26) used[i] = 0;
		rep(i,26) if(mt[i][1] != -1 && isSafe(i,count-1)) break;

		printf("%s\n",count!=0 && i==26 ? "SUSPICIOUS" : "SAFE");
	}

	return 0;
}