Problem:


X-Ray Screening System

これは 20XX 年の話である．再生発電網による安定したエネルギー供給，および液化合成燃料の発明によって航空旅客数は鰻登りに増加した．しかし，航空機によるテロリズムの脅威は依然として存在するため，高速でかつ高い信頼性をもつ自動手荷物検査システムの重要性が高まっている．検査官が全部の荷物を調べることは実際問題として困難であることから，自動検査において疑わしいと判断された手荷物だけを検査官で改めて調べるという仕組みを整えたいわけである．

航空機業界からの要請を受け，国際客室保護会社（International Cabin Protection Company）では，新たな自動検査システムを開発するため，最近の旅客の手荷物について調査した．調査の結果，最近の旅客の手荷物には次のような傾向があることが判明した．

手荷物は 1 辺だけが短い直方体のような形状をしている．

一般の乗客が手荷物に詰めて航空機に持ち込む品物としてはノートパソコン，音楽プレイヤー，携帯ゲーム機，トランプなどがあり，これらはいずれも長方形である．

個々の品物は，その長方形の辺が手荷物の辺と平行になるように詰めこまれる．

一方，テロリズムに用いられるような武器は，長方形とは非常に異なる形状をもつ．

上記の調査結果をふまえて，以下のような手荷物検査のためのモデルを考案した．それぞれの手荷物は X 線に対して透明である直方体の容器だとみなす．その中には X 線に対して不透明である複数の品物が入っている．ここで，直方体の 3 辺を x 軸，y 軸，z 軸とする座標系を考え，x 軸と平行な方向に X 線を照射して，y-z 平面に投影された画像を撮影する．撮影された画像は適当な大きさの格子に分割され，画像解析によって，それぞれの格子領域に映っている品物の材質が推定される．この会社には非常に高度の解析技術があり，材質の詳細な違いすらも解析することが可能であることから，品物の材質は互いに異なると考えることができる．なお，複数の品物が x 軸方向に関して重なっているときは，それぞれの格子領域について最も手前にある，すなわち x 座標が最小である品物の材質が得られる．また，2 つ以上の品物の x 座標が等しいことはないと仮定する．

あなたの仕事は，画像解析の結果が与えられたときに，長方形ではない（武器であるかもしれない）品物が入っていることが断言できるか，あるいはその手荷物には長方形の品物以外のものは入っていないと推測されるかを判定するプログラムを作成することである．

Input

入力の先頭行には単一の正の整数が含まれ，これはデータセットの個数を表す．それぞれのデータセットは次の形式で与えられる．

H W

解析結果その1

解析結果その2

...

解析結果そのH

H は画像の縦の大きさ，W は横の大きさを表す整数である (1 <= h , w <= 50)．解析結果の各行は W 文字で構成されており，i 番目の文字は，行の左から i 番目にある格子領域における解析結果を表す．物質が検出された格子領域については，その材質が英大文字（A〜Z）によって表される．このとき，同じ材質であれば同じ文字が，また異なる材質であれば異なる文字が用いられる．物質が検出されなかった格子領域についてはドット（.）で表される．

すべてのデータセットについて，材質の種類は 7 種類を超えないことが保証されている．

Output

それぞれのデータセットに対して，長方形以外の品物が確実に入っているときは「SUSPICIOUS」を，そうでないときは「SAFE」をそれぞれ 1 行に出力しなさい．

Sample Input

6
1 1
.
3 3
...
.W.
...
10 10
..........
.DDDDCCC..
.DDDDCCC..
.DDDDCCC..
ADDDDCCC..
AAA..CCC..
AAABBBBC..
AAABBBB...
..BBBBB...
..........
10 10
..........
.DDDDDD...
.DDDDCCC..
.DDDDCCC..
ADDDDCCC..
AAA..CCC..
AAABBBBC..
AAABBBB...
..BBBBB...
..........
10 10
R..E..C.T.
R.EEE.C.T.
.EEEEE....
EEEEEEE...
.EEEEEEE..
..EEEEEEE.
...EEEEEEE
....EEEEE.
.....EEE..
......E...
16 50
..................................................
.........AAAAAAAAAAAAAAAA.........................
....PPP...AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.....
....PPP...AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.....
....PPP...AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA....
....PPP..............AAAAA.AAAAAAAAAAAAAAAA.......
....PPP................A....AAA.AAAAAAAAAA........
....PPP...........IIIIIAAIIAIII.AAAAAAAAAA........
..CCCCCCCCCCCCC...IIIIIIAAAAAAAAAAAAAAAAAA........
..CCCCCCCCCCCCC...IIIIIIIIIIIII...AAAAAAAAAA......
....PPP............................AAAAAAAAAA.....
MMMMPPPMMMMMMMMMMMMMMM.............AAAAAAAAAAA....
MMMMPPPMMMMMMMMMMMMMMM..............AAAAAAAAAAA...
MMMMMMMMMMMMMMMMMMMMMM...............AAAAAAAAAA...
MMMMMMMMMMMMMMMMMMMMMM...............AAAAAAAAAA...
MMMMMMMMMMMMMMMMMMMMMM............................

Output for the Sample Input

SAFE
SAFE
SAFE
SUSPICIOUS
SUSPICIOUS
SUSPICIOUS



Sample input:
6
1 1
.
3 3
...
.W.
...
10 10
..........
.DDDDCCC..
.DDDDCCC..
.DDDDCCC..
ADDDDCCC..
AAA..CCC..
AAABBBBC..
AAABBBB...
..BBBBB...
..........
10 10
..........
.DDDDDD...
.DDDDCCC..
.DDDDCCC..
ADDDDCCC..
AAA..CCC..
AAABBBBC..
AAABBBB...
..BBBBB...
..........
10 10
R..E..C.T.
R.EEE.C.T.
.EEEEE....
EEEEEEE...
.EEEEEEE..
..EEEEEEE.
...EEEEEEE
....EEEEE.
.....EEE..
......E...
16 50
..................................................
.........AAAAAAAAAAAAAAAA.........................
....PPP...AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.....
....PPP...AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.....
....PPP...AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA....
....PPP..............AAAAA.AAAAAAAAAAAAAAAA.......
....PPP................A....AAA.AAAAAAAAAA........
....PPP...........IIIIIAAIIAIII.AAAAAAAAAA........
..CCCCCCCCCCCCC...IIIIIIAAAAAAAAAAAAAAAAAA........
..CCCCCCCCCCCCC...IIIIIIIIIIIII...AAAAAAAAAA......
....PPP............................AAAAAAAAAA.....
MMMMPPPMMMMMMMMMMMMMMM.............AAAAAAAAAAA....
MMMMPPPMMMMMMMMMMMMMMM..............AAAAAAAAAAA...
MMMMMMMMMMMMMMMMMMMMMM...............AAAAAAAAAA...
MMMMMMMMMMMMMMMMMMMMMM...............AAAAAAAAAA...
MMMMMMMMMMMMMMMMMMMMMM............................


Sample output:
SAFE
SAFE
SAFE
SUSPICIOUS
SUSPICIOUS
SUSPICIOUS

Submission status: Wrong Answer

Solution code:
class Baggage:

    height = 0
    width = 0
    contentsdata = [[]]

    def __init__(self, H, W):
        self.height = H
        self.width = W
        self.contentsdata = [["." for i in range(0, H)] for j in range(0, W)]

    def setContents(self, x, y, cnt):
        self.contentsdata[x][y] = cnt


def contentscheck(baggage, checkwords):  # ????????? => True???????????¢???=> False
    left = 10000
    right = 10000
    up = 1000
    bottom = 1000
    for x in range(0, baggage.width):  # ???????????????????????¨?????????????????????????????????
        if(baggage.contentsdata[x].count(checkwords) > 0):
            left = x
            break
    for x in sorted([int(i) for i in range(0, baggage.width)], reverse=True):  # ???????????????????????¨?????????????????????????????????
        if(baggage.contentsdata[x].count(checkwords) > 0):
            right = x
            break
    for y in range(0, baggage.height):  # ???????????????????????¨?????????????????????????????????
        for x in range(0, baggage.width):
            if(baggage.contentsdata[x][y] == checkwords):
                up = y
                break
        else:
            continue
        break
    for y in sorted([int(i) for i in range(0, baggage.height)], reverse=True):  # ???????????????????????¨?????????????????????????????????
        for x in range(0, baggage.width):
            if(baggage.contentsdata[x][y] == checkwords):
                bottom = y
                break
        else:
            continue
        break
    # print(checkwords + ": (left, right, up, bottom) = (" + str(left) + ", " + str(right) + ", " + str(up) + ", " + str(bottom) + ")")
    for x in range(left, right + 1):
        for y in range(up, bottom + 1):
            if(baggage.contentsdata[x][y] == "."):
                return True
                break
        else:
            continue
        break
    return False


n = int(input())
usedwordslist = []

for k in range(0, n):
    try:
        size = [int(i) for i in input().split(" ")]  # size = [H, W]
        checkingbaggage = Baggage(size[0], size[1])
        for i in range(0, size[0]):
            data = list(input())
            for j in range(0, size[1]):
                checkingbaggage.contentsdata[j][i] = data[j]
                if(data[j] != "." and usedwordslist.count(data[j]) == 0):
                    usedwordslist.append(data[j])
        usedwordslist.sort()
        for i in usedwordslist:
            if(contentscheck(checkingbaggage, i)):
                print("SUSPICIOUS")
                break
        else:
            print("SAFE")
    except:
        raise
        exit()
    '''???????????\????¢??????¨
    for i in range(0, size[0]):
            for j in range(0, size[1]):
                print(checkingbaggage.contentsdata[j][i])
    print(usedwordslist)'''
    usedwordslist.clear()

Submission status: Wrong Answer

Solution code:
class Baggage:

    height = 0
    width = 0
    contentsdata = [[]]

    def __init__(self, H, W):
        self.height = H
        self.width = W
        self.contentsdata = [["." for i in range(0, H)] for j in range(0, W)]

    def setContents(self, x, y, cnt):
        self.contentsdata[x][y] = cnt


def contentscheck(baggage, checkwords):  # ????????? => True???????????¢???=> False
    left = 10000
    right = 10000
    up = 1000
    bottom = 1000
    for x in range(0, baggage.width):  # ???????????????????????¨?????????????????????????????????
        if(baggage.contentsdata[x].count(checkwords) > 0):
            left = x
            break
    for x in sorted([int(i) for i in range(0, baggage.width)], reverse=True):  # ???????????????????????¨?????????????????????????????????
        if(baggage.contentsdata[x].count(checkwords) > 0):
            right = x
            break
    for y in range(0, baggage.height):  # ???????????????????????¨?????????????????????????????????
        for x in range(0, baggage.width):
            if(baggage.contentsdata[x][y] == checkwords):
                up = y
                break
        else:
            continue
        break
    for y in sorted([int(i) for i in range(0, baggage.height)], reverse=True):  # ???????????????????????¨?????????????????????????????????
        for x in range(0, baggage.width):
            if(baggage.contentsdata[x][y] == checkwords):
                bottom = y
                break
        else:
            continue
        break
    # print(checkwords + ": (left, right, up, bottom) = (" + str(left) + ", " + str(right) + ", " + str(up) + ", " + str(bottom) + ")")
    complite = 1
    for x in range(left, right + 1):
        for y in range(up, bottom + 1):
            if(baggage.contentsdata[x][y] != checkwords):
                complite = 0
            if(baggage.contentsdata[x][y] == "."):
                return True
                break
        else:
            continue
        break
    if(complite == 1):
        return 2
    else:
        return False


n = int(input())
usedwordslist = []
cmp = False

for k in range(0, n):
    try:
        size = [int(i) for i in input().split(" ")]  # size = [H, W]
        checkingbaggage = Baggage(size[0], size[1])
        for i in range(0, size[0]):
            data = list(input())
            for j in range(0, size[1]):
                checkingbaggage.contentsdata[j][i] = data[j]
                if(data[j] != "." and usedwordslist.count(data[j]) == 0):
                    usedwordslist.append(data[j])
        usedwordslist.sort()
        for i in usedwordslist:
            jdg = contentscheck(checkingbaggage, i)
            if(jdg == True):
                print("SUSPICIOUS")
                break
            if(jdg == "2"):
                cmp = True
        else:
            if(cmp == True):
                print("SAFE")
            else:
                print("SUSPICIOUS")
    except:
        raise
        exit()
    '''???????????\????¢??????¨
    for i in range(0, size[0]):
            for j in range(0, size[1]):
                print(checkingbaggage.contentsdata[j][i])
    print(usedwordslist)'''
    usedwordslist.clear()

Submission status: Wrong Answer

Solution code:
class Baggage:

    height = 0
    width = 0
    contentsdata = [[]]

    def __init__(self, H, W):
        self.height = H
        self.width = W
        self.contentsdata = [["." for i in range(0, H)] for j in range(0, W)]

    def setContents(self, x, y, cnt):
        self.contentsdata[x][y] = cnt


def contentscheck(baggage, checkwords):  # ????????? => 0???????????¢???????????§???=> 1 ?????¨???????????¢???=> 2
    left = 0
    right = 0
    up = 0
    bottom = 0
    for x in range(0, baggage.width):  # ???????????????????????¨?????????????????????????????????
        if(baggage.contentsdata[x].count(checkwords) > 0):
            left = x
            break
    for x in sorted([int(i) for i in range(0, baggage.width)], reverse=True):  # ???????????????????????¨?????????????????????????????????
        if(baggage.contentsdata[x].count(checkwords) > 0):
            right = x
            break
    for y in range(0, baggage.height):  # ???????????????????????¨?????????????????????????????????
        for x in range(0, baggage.width):
            if(baggage.contentsdata[x][y] == checkwords):
                up = y
                break
        else:
            continue
        break
    for y in sorted([int(i) for i in range(0, baggage.height)], reverse=True):  # ???????????????????????¨?????????????????????????????????
        for x in range(0, baggage.width):
            if(baggage.contentsdata[x][y] == checkwords):
                bottom = y
                break
        else:
            continue
        break
    # print(checkwords + ": (left, right, up, bottom) = (" + str(left) + ", " + str(right) + ", " + str(up) + ", " + str(bottom) + ")")
    complite = 1
    for x in range(left, right + 1):
        for y in range(up, bottom + 1):
            # print(checkwords + ":" + baggage.contentsdata[x][y])
            if(baggage.contentsdata[x][y] != checkwords):
                complite = 0
            if(baggage.contentsdata[x][y] == "."):
                return 0
                break
        else:
            continue
        break
    if(complite == 0):
        return 1
    else:
        return 2


n = int(input())
usedwordslist = []

for k in range(0, n):
    cmp = False
    try:
        size = [int(i) for i in input().split(" ")]  # size = [H, W]
        checkingbaggage = Baggage(size[0], size[1])
        for i in range(0, size[0]):
            data = list(input())
            for j in range(0, size[1]):
                checkingbaggage.contentsdata[j][i] = data[j]
                if(data[j] != "." and usedwordslist.count(data[j]) == 0):
                    usedwordslist.append(data[j])
        usedwordslist.sort()

        for i in usedwordslist:
            jdg = int(contentscheck(checkingbaggage, i))
            if(jdg == 0):
                print("SUSPICIOUS")
                break
            if(jdg == 2):
                cmp = True
        else:
            print("cmp " + str(cmp))
            if(cmp):
                print("SAFE")
            elif(len(usedwordslist) == 0):
                print("SAFE")
            else:
                print("SUSPICIOUS")
    except:
        raise
        exit()
    '''???????????\????¢??????¨
    for i in range(0, size[0]):
            for j in range(0, size[1]):
                print(checkingbaggage.contentsdata[j][i])
    print(usedwordslist)'''
    usedwordslist.clear()

Submission status: Wrong Answer

Solution code:
class Baggage:

    height = 0
    width = 0
    contentsdata = [[]]

    def __init__(self, H, W):
        self.height = H
        self.width = W
        self.contentsdata = [["." for i in range(0, H)] for j in range(0, W)]

    def setContents(self, x, y, cnt):
        self.contentsdata[x][y] = cnt


def contentscheck(baggage, checkwords):  # ????????? => 0???????????¢???????????§???=> 1 ?????¨???????????¢???=> 2
    left = 0
    right = 0
    up = 0
    bottom = 0
    for x in range(0, baggage.width):  # ???????????????????????¨?????????????????????????????????
        if(baggage.contentsdata[x].count(checkwords) > 0):
            left = x
            break
    for x in sorted([int(i) for i in range(0, baggage.width)], reverse=True):  # ???????????????????????¨?????????????????????????????????
        if(baggage.contentsdata[x].count(checkwords) > 0):
            right = x
            break
    for y in range(0, baggage.height):  # ???????????????????????¨?????????????????????????????????
        for x in range(0, baggage.width):
            if(baggage.contentsdata[x][y] == checkwords):
                up = y
                break
        else:
            continue
        break
    for y in sorted([int(i) for i in range(0, baggage.height)], reverse=True):  # ???????????????????????¨?????????????????????????????????
        for x in range(0, baggage.width):
            if(baggage.contentsdata[x][y] == checkwords):
                bottom = y
                break
        else:
            continue
        break
    # print(checkwords + ": (left, right, up, bottom) = (" + str(left) + ", " + str(right) + ", " + str(up) + ", " + str(bottom) + ")")
    complite = 1
    for x in range(left, right + 1):
        for y in range(up, bottom + 1):
            # print(checkwords + ":" + baggage.contentsdata[x][y])
            if(baggage.contentsdata[x][y] != checkwords):
                complite = 0
            if(baggage.contentsdata[x][y] == "."):
                return 0
                break
        else:
            continue
        break
    if(complite == 0):
        return 1
    else:
        return 2


n = int(input())
usedwordslist = []

for k in range(0, n):
    cmp = False
    try:
        size = [int(i) for i in input().split(" ")]  # size = [H, W]
        checkingbaggage = Baggage(size[0], size[1])
        for i in range(0, size[0]):
            data = list(input())
            for j in range(0, size[1]):
                checkingbaggage.contentsdata[j][i] = data[j]
                if(data[j] != "." and usedwordslist.count(data[j]) == 0):
                    usedwordslist.append(data[j])
        usedwordslist.sort()

        for i in usedwordslist:
            jdg = int(contentscheck(checkingbaggage, i))
            if(jdg == 0):
                print("SUSPICIOUS")
                break
            if(jdg == 2):
                cmp = True
        else:
            if(cmp):
                print("SAFE")
            elif(len(usedwordslist) == 0):
                print("SAFE")
            else:
                print("SUSPICIOUS")
    except:
        raise
        exit()
    '''???????????\????¢??????¨
    for i in range(0, size[0]):
            for j in range(0, size[1]):
                print(checkingbaggage.contentsdata[j][i])
    print(usedwordslist)'''
    usedwordslist.clear()

Submission status: Wrong Answer

Solution code:
def is_safe(image, p):
    count = 0
    for k, v in p.items():
        rect = True
        for y in range(v[1], v[3] + 1, 1):
            for x in range(v[0], v[2] + 1, 1):
                m = image[y][x]
                if m == '.':
                    return False
                if k != m:
                    rect = False
        if rect:
            count += 1
    return count > 0
n = int(input())
for i in range(n):
    h, w = map(int, input().split(' '))
    image = [input() for y in range(h)]
    p = {}
    for y in range(h):
        for x in range(w):
            m = image[y][x]
            if m == '.':
                continue
            if m not in p:
                p[m] = [x, y, x, y]
            else:
                p[m][0] = min(p[m][0], x)
                p[m][1] = min(p[m][1], y)
                p[m][2] = max(p[m][2], x)
                p[m][3] = max(p[m][3], y)
    print('SAFE' if is_safe(image, p) else 'SUSPICIOUS')

Submission status: Accepted

Solution code:
for t in xrange(input()):
    h, w = map(int, raw_input().split())
    A = [list(raw_input()) for i in xrange(h)]
    xmin = {}; xmax = {}
    ymin = {}; ymax = {}
    obj = set()
    for i in xrange(h):
        for j in xrange(w):
            c = A[i][j]
            if c == '.': continue
            xmin[c] = min(xmin.get(c, 99), j)
            xmax[c] = max(xmax.get(c, -1), j)
            ymin[c] = min(ymin.get(c, 99), i)
            ymax[c] = max(ymax.get(c, -1), i)
            obj.add(c)
    if not obj:
        print "SAFE"
        continue
    ok = 1
    g = {e: set() for e in obj}
    deg = {e: 0 for e in obj}
    for q in obj:
        for i in xrange(ymin[q], ymax[q]+1):
            for j in xrange(xmin[q], xmax[q]+1):
                c = A[i][j]
                if c == '.':
                    ok = 0
                    break
                if c != q:
                    g[q].add(c)
            if not ok: break
        if not ok: break
    if not ok:
        print "SUSPICIOUS"
        continue
    for e in obj:
        for t in g[e]:
            deg[t] += 1
    cnt = len(obj)
    used = set()
    for e in obj:
        for e in obj:
            if not deg[e] and e not in used:
                for t in g[e]:
                    deg[t] -= 1
                used.add(e)
                cnt -= 1
    if cnt:
        print "SUSPICIOUS"
    else:
        print "SAFE"

Submission status: Accepted

Solution code:
def isRect(data,dic):
  for d in dic.items():
    isValid=True
    for i in xrange(d[1][0],d[1][2]+1):
      for j in xrange(d[1][1],d[1][3]+1):
        if not (data[i][j]==d[0] or data[i][j]=="*") :
          isValid=False
    if isValid: return d[0]
  return "-"

def checker(data,dic):
  while len(dic)>0:
    r=isRect(data,dic)
    if r=="-":
      print "SUSPICIOUS"
      return
    else:
      for i in xrange(dic[r][0],dic[r][2]+1):
        for j in xrange(dic[r][1],dic[r][3]+1):
          data[i][j]="*"
      del dic[r]
  print "SAFE"


T=int(raw_input())
for _ in xrange(T):
  H,W=map(int,raw_input().split())
  data=[["-"]*W for _ in xrange(H)]
  dic={}
  for i in xrange(H):
    s=raw_input()
    for j in xrange(W):
      data[i][j]=s[j]
      if s[j] not in dic:
        dic[s[j]]=(i,j,i,j)
      else:
        dic[s[j]]=(min(dic[s[j]][0],i),min(dic[s[j]][1],j),max(dic[s[j]][2],i),max(dic[s[j]][3],j))
  checker(data, dic)

Submission status: Accepted

Solution code:
def can_fill(image, k, v):
    for y in range(v[1], v[3] + 1):
        for x in range(v[0], v[2] + 1):
            m = image[y][x]
            if m != k and m != '*':
                return False
    return True

def is_safe(image, p):
    keys = list(p.keys())
    i = 0
    while i < len(keys):
        k = keys[i]
        v = p[k]
        if can_fill(image, k, v):
            for y in range(v[1], v[3] + 1):
                for x in range(v[0], v[2] + 1):
                    image[y][x] = '*'
            keys.remove(k)
            i = 0
        else:
            i += 1
    return len(keys) == 0

n = int(input())
for i in range(n):
    h, w = map(int, input().split(' '))
    image = [list(input()) for y in range(h)]
    p = {}
    for y in range(h):
        for x in range(w):
            m = image[y][x]
            if m != '.':
                if m not in p:
                    p[m] = [x, y, x, y]
                else:
                    p[m][0] = min(p[m][0], x)
                    p[m][1] = min(p[m][1], y)
                    p[m][2] = max(p[m][2], x)
                    p[m][3] = max(p[m][3], y)
    print('SAFE' if is_safe(image, p) else 'SUSPICIOUS')

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    n = I()
    ni = 0

    while ni < n:
        ni += 1
        h,w = LI()
        s = [[c for c in S()] for _ in range(h)]
        d = collections.defaultdict(lambda: [inf,-inf,inf,-inf])
        for i in range(h):
            for j in range(w):
                if s[i][j] == '.':
                    continue
                t = d[s[i][j]]
                if t[0] > i:
                    t[0] = i
                if t[1] < i:
                    t[1] = i
                if t[2] > j:
                    t[2] = j
                if t[3] < j:
                    t[3] = j
        f = True
        k = set(d.keys())
        while f:
            f = False
            for t in list(k):
                hi,ha,wi,wa = d[t]
                ff = True
                for i in range(hi,ha+1):
                    for j in range(wi,wa+1):
                        if s[i][j] != t and s[i][j] != '?':
                            ff = False
                            break
                    if not ff:
                        break
                if ff:
                    k.remove(t)
                    f = True
                    for i in range(hi,ha+1):
                        for j in range(wi,wa+1):
                            s[i][j] = '?'
        if not k:
            rr.append('SAFE')
        else:
            rr.append('SUSPICIOUS')

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
n = int(input())
for _ in range(n):
  h, w = map(int, input().split())
  mp = [list(input()) for _ in range(h)]
  range_dic = {}
  keys = []
  for y in range(h):
    for x in range(w):
      c = mp[y][x]
      if c in range_dic:
        x1, x2, y1, y2 = range_dic[c]
        range_dic[c] = (min(x, x1), max(x, x2), min(y, y1), max(y, y2))
      else:
        range_dic[c] = (x, x, y, y)
        keys.append(c)
  
  while keys:
    tmp = keys[:]
    for key in keys:
      break_flag = False
      x1, x2, y1, y2 = range_dic[key]
      for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
          if not mp[y][x] in (key, "#"):
            break_flag = True
            break
        if break_flag:
          break
      else:
        for x in range(x1, x2 + 1):
          for y in range(y1, y2 + 1):
            mp[y][x] = "#"
        keys.remove(key)
    
    if tmp == keys:
      print("SUSPICIOUS")
      break
  
  else:
    print("SAFE")

Submission status: Accepted

Solution code:
n = int(input())
for _ in range(n):
  h, w = map(int, input().split())
  mp = [list(input()) for _ in range(h)]
  range_dic = {}
  keys = []
  for y in range(h):
    for x in range(w):
      c = mp[y][x]
      if c in range_dic:
        x1, x2, y1, y2 = range_dic[c]
        range_dic[c] = (min(x, x1), max(x, x2), min(y, y1), max(y, y2))
      else:
        range_dic[c] = (x, x, y, y)
        keys.append(c)
  
  while keys:
    tmp = keys[:]
    for key in keys:
      break_flag = False
      x1, x2, y1, y2 = range_dic[key]
      for x in range(x1, x2 + 1):
        for y in range(y1, y2 + 1):
          if not mp[y][x] in (key, "#"):
            break_flag = True
            break
        if break_flag:
          break
      else:
        for y in range(y1, y2 + 1):
          mp[y][x1:x2 + 1] = ["#"] * (x2 - x1 + 1)
        keys.remove(key)
    
    if tmp == keys:
      print("SUSPICIOUS")
      break
  
  else:
    print("SAFE")

Submission status: Accepted

Solution code:
from itertools import permutations

def solve():    
    for ch in permutations(set(list("".join(field))) - set(["."])):
        cp = map(list,field[:])
        for c in ch:
            if check(cp, c) == False:
                break
        else:
            return "SAFE"
    return "SUSPICIOUS"
            
def check(field, c):
    for y in xrange(corner[c][2], corner[c][3] + 1):
        for x in xrange(corner[c][0], corner[c][1] + 1):
            if field[y][x] != c and field[y][x] != "*":
                return False
            field[y][x] = "*"
    return True

for _ in xrange(input()):
    h, w = map(int, raw_input().split())
    if h | w == 0:
        break    
    field = [raw_input() for _ in xrange(h)]
    corner = {}
    for y in xrange(h):
        for x in xrange(w):
            if field[y][x] == ".":
                continue
            if field[y][x] not in corner:
                corner[field[y][x]] = [x, x, y, y] # left right top buto
            else:
                corner[field[y][x]][0] = min(corner[field[y][x]][0], x)
                corner[field[y][x]][1] = max(corner[field[y][x]][1], x)
                corner[field[y][x]][2] = min(corner[field[y][x]][2], y)
                corner[field[y][x]][3] = max(corner[field[y][x]][3], y)
    print solve()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


def dfs(s,cnt):
    global ans
    if cnt > 10:
        ans = False
        return
    for t in lines[s]:
        dfs(t,cnt+1)


N = inp()
for _ in range(N):
    H,W = inpl()
    MAP = [['.']*(W+2)] + [['.']+list(input())+['.'] for y in range(H)] + [['.']*(W+2)]

    als = set([])
    almm = [[INF,0,INF,0] for _ in range(30)]
    for y in range(1,H+1):
        for x in range(1,W+1):
            tmp = MAP[y][x]
            if tmp != '.':
                tmp = ord(tmp) - ord('A')
                als.add(tmp)
                almm[tmp][0] = min(almm[tmp][0],x)
                almm[tmp][1] = max(almm[tmp][1],x)
                almm[tmp][2] = min(almm[tmp][2],y)
                almm[tmp][3] = max(almm[tmp][3],y)

    ans = True
    lines = defaultdict(set)
    for a in als:
        xl,xr,yl,yr = almm[a]
        alpha = chr(a+ord('A'))
        for x in range(xl,xr+1):
            for y in range(yl,yr+1):
                if MAP[y][x] == '.':
                    ans = False
                    break
                elif MAP[y][x] != alpha:
                    lines[a].add(ord(MAP[y][x])-ord('A'))

    for a in als:
        dfs(a,0)


    if not ans:
        print('SUSPICIOUS')
    else:
        print('SAFE')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#aoj b
import re
from collections import defaultdict

def check(i):#メモ化再帰
    if d[i] > 0:
        return d[i]
    d[i] = 1#チェック状態
    for y in range(p[i][0],p[i][1]+1):
        for x in range(p[i][2],p[i][3]+1):
            if s[y][x] == ".":#長方形内部に空の部分が存在
                d[i] = 3 #SUSPICIOUS
                return d[i]
            elif s[y][x] != i:#長方形内部に他の物質が存在
                if d[s[y][x]] == 1:#その物質がチェック状態
                    d[i] = 3 #SUSPICIOUS(循環参照 テストケース4)
                    return d[i]
                c = check(s[y][x])#そいつの状態確認の再帰
                if c == 3:
                    d[i] == 3
                    return d[i]
    d[i] = 2#SAFE
    return 2

N = int(input())
for _ in range(N):
    h,w = map(int,input().split())
    s = [list(input()) for _ in range(h)]
    p = defaultdict(list)
    #p[0]:上端,p[1]:下端,p[2]:左端,p[3]:右端
    #y座標の追加は横方向で見る(上端は上から、下端は下から)
    for y in range(h):#上端
        for x in range(w):
            if s[y][x] != '.' and len(p[s[y][x]]) < 1:
                p[s[y][x]].append(y)
    for y in range(h)[::-1]:#下端
        for x in range(w):
            if s[y][x] != '.' and len(p[s[y][x]]) < 2:
                p[s[y][x]].append(y)
    #x座標の追加は縦方向で見る(左端は左から、右端は右から)
    for x in range(w):#左端
        for y in range(h):
            if s[y][x] != '.' and len(p[s[y][x]]) < 3:
                p[s[y][x]].append(x)
    for x in range(w)[::-1]:#右端
        for y in range(h):
            if s[y][x] != '.' and len(p[s[y][x]]) < 4:
                p[s[y][x]].append(x)
    d = defaultdict(lambda : 0)#メモ化再帰用dict
    for i in p.keys():
        if check(i) == 3:
            print('SUSPICIOUS')
            break
    else:
        print('SAFE')