ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2002 X-Ray Screening System

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2002


・概要
手荷物の中に危険物が入っているかどうかを判定する問題です。
詳しくは問題文を...


・解法
全探索 + 枝刈りで解くことができます。

手荷物に入っている物の数は最大7種類で重なり方は7!通りあるので、途中で安全だと分かればそこで探索を終了させます。

探索のやり方ですが、
まずすべての物が長方形と仮定して、矛盾が生じないかどうかを判定します。

int p[26][4]には長方形と仮定したときの座標の最大値と最小値を保存させておきます。(※ちなみに配列の26という値はアルファベットあA~Zの個数です)


ソースコード

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int H,W,N;
int p[26][4]; // p[][xMin], p[][xMax], p[][yMin], p[][yMax]
char G[50][50];
bool ans;
bool used[26];

void dfs(int cnt){
   if(ans) return;
   
   if(cnt==N){
      ans = true;
      return;
   }

   for(int k = 0 ; k < 26 ; k++){
      if(used[k]) continue;

      for(int i = p[k][0] ; i <= p[k][1] ; i++){
	 for(int j = p[k][2] ; j <= p[k][3] ; j++){
	    if(G[i][j]=='.') return;
	    if((G[i][j]-'A')!=k && used[G[i][j]-'A'])return;
	 }
      }

      used[k] = true;
      dfs(cnt+1);
      used[k] = false;
   }
}
 
int main(){
   int T;
   cin >> T;
   while(T--){
      cin >> H >> W;

      for(int i = 0 ; i < H ; i++){
	 for(int j = 0 ; j < W ; j++){
	    cin >> G[i][j];
	 }
      }
      
      for(int i = 0 ; i < 26 ; i++){
	 p[i][0] = p[i][2] = 1000;
	 p[i][1] = p[i][3] = 0;
      }

      N = 0;
      ans = false;
      memset(used, true, sizeof(used));
      
      for(int i = 0 ; i < H ; i++){
	 for(int j = 0 ; j < W ; j++){
	    if(G[i][j]=='.')continue;
	    int idx = G[i][j] - 'A';
	    p[idx][0] = min(p[idx][0], i);
	    p[idx][1] = max(p[idx][1], i);
	    p[idx][2] = min(p[idx][2], j);
	    p[idx][3] = max(p[idx][3], j);
	    if(used[idx]){
	       N++;
	       used[idx] = false;
	    }
 	 }
      }
    
      dfs(0);

      cout << ((ans) ? "SAFE" : "SUSPICIOUS") << endl;
   }
   return 0;
}