AOJ 2002:X-Ray Screening System

問題リンク：X-Ray Screening System | Aizu Online Judge

問題概要：
与えられたインプットの中に確実に長方形でないものが存在するかどうか判定せよ

解法：
SAFEなのであれば少なくとも１つは長方形が存在する（そもそも何も入っていない場合を除く）はずなのでそれを確認する
その長方形をチェックした事によって長方形であることが判明するものがでてきたのであればそれもチェックする
これを繰り返し、すべて確認し終った時に全てが長方形であったならばSAFEとした

長方形かどうかの判定はその図中に存在する対象物の座標のうち一番左にあるものと一番右にあるもの、一番上にあるものと一番した二あるものをとってきて
for i top から bottomまで
for j left から　rightまで
if インプット[i][j] != 対象物 && チェックされていない
長方形でない
とした

ちなみに以下に書いたような感じのインプットではまってた

....
....
A.A.

もちろんSUSPICIOUSです

コード：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
int h,w;
string G[51];
bool checked[51][51];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

bool isRect(int x,int y)
{
  int x1,x2,y1,y2;
  x1 = x2 = x;
  y1 = y2 = y;

  rep(i,h)
    rep(j,w)
    {
      if(G[i][j] == G[y][x])
	{
	  if(j < x1)x1 = j;
	  if(j > x2)x2 = j;
	  if(i < y1)y1 = i;
	  if(i > y2)y2 = i;
	}
    }

  REP(i,y1,y2+1)
    REP(j,x1,x2+1)
    if(G[i][j] != G[y][x] && !checked[i][j])return false;
  return true;

}

void draw(int x,int y,char c)
{
  if(checked[y][x])return;
  checked[y][x] = true;
  rep(i,4)
    {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(!(0 <= nx && nx < w && 0 <= ny && ny < h))continue;
      if(G[ny][nx] != c)continue;
      draw(nx,ny,c);
    }
}

bool isSafe()
{
  rep(i,h)
    rep(j,w)
    if(G[i][j] != '.' && !checked[i][j])return false;
  return true;
}

int main()
{
  int T;
  cin >> T;
  while(T-- > 0)
    {
      cin >> h >> w;
      rep(i,h)
	cin >> G[i];
      rep(i,51)rep(j,51)checked[i][j] = false;

      while(true)
	{
	  bool Fin = true;
	  bool update = false;
       
	  rep(i,h)
	    {	
	      rep(j,w)
		{
		  if(G[i][j] == '.')continue;
		  if(checked[i][j])continue;
		  Fin = false;
		  if(isRect(j,i))
		    {
		      update = true;
		      draw(j,i,G[i][j]);
		    }
		}
	    }
	  if(Fin || !update)break;
	}
   
      isSafe()?cout << "SAFE" << endl:cout << "SUSPICIOUS" << endl;
    }
  return 0;
}