Problem:


塗りつぶしゲーム

指で画面にタッチして操作することのできるタブレットインターフェースの技術は、ゲームの分野でも応用され、新しい操作感を持つ様々な種類のゲームが作られています。現在、ＡＺ社が開発しているゲームもその一つです。

このソフトウェア（ゲーム）の要件は以下の通りです。

 画面には X 列&times; Y行の2次元グリッドがあります。

 グリッドのセルは赤(R)、緑(G)、茶(B)の3色のいずれかで塗られています。

 セルの色を変更するボタンR、G、Bがあり、このボタンが押下されると一番左上(0,0)のセルがその色に変更されます。

 一番左上のセルの色が変更されると、そのセルの元の色と同じ色に塗られた隣接するすべてのセルが指定された色に変わります。すなわち、元の色が同じ色のセルでつながったセルはすべて指定された色に変更されます。

このようにグリッドを塗りつぶしていき、最終的にグリッド全体を一色にするというゲームです。少ない手順で解くと高得点が与えられます。

ＡＺ社のプログラマーであるあなたは、このゲームのロジックの一部分を開発することになりました。まずは、この最高得点を計算するため、このゲームを最短で解いた場合、最低何回選択ボタンを操作すればグリッドが一色になるかをもとめるプログラムを作ることにしました。

入力

複数のデータセットが与えられます。入力の終わりはゼロふたつで示されます。各データセットは以下の形式で与えられます。

X Y
c1,1 c2,1 ... cX,1
c1,2 c2,2 ... cX,2
:
c1,Y c2,Y ... cX,Y

1行目にグリッドの列と行のサイズ X, Y (2 ≤ X, Y ≤ 10) が与えられます。続く Y 行に i 列目 j 行目のセルの色を表す文字 ci,j が空白区切りで与えられます。

出力

データセットごとに、ボタン操作の最少回数を1行に出力します。

入力例

3 3
R G B
G G G
G B B
2 4
R G
G G
R B
B R
4 3
G G B R
G R R G
B G G R
0 0

出力例

2
4
4



Sample input:
3 3
R G B
G G G
G B B
2 4
R G
G G
R B
B R
4 3
G G B R
G R R G
B G G R
0 0


Sample output:
2
4
4

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def paintout(s, color):
    cnt, pre_color, h, w = 0, s[0][0], len(s), len(s[0])

    que = deque([(0, 0)])
    while len(que):
        x, y = que.pop()
        if 0 <= x < w and 0 <= y < h and s[y][x] == pre_color:
            s[y][x] = color
            cnt +=1
            que.extend(((x-1,y),(x,y-1),(x+1,y),(x,y+1)))

    return cnt

from copy import deepcopy
def dfs(depth, s, pre_cnt):
    ret = []
    pre_color, h, w = s[0][0], len(s), len(s[0])
    
    colors = [0,1,2]
    colors.remove(pre_color)
    
    for color in colors:
        p = deepcopy(s)
        cnt = paintout(p,color)
        if cnt == h * w:
            return 0
        if cnt == pre_cnt:
            return float('inf')
        ret.append(dfs(depth + 1, p, cnt))

    return min(ret) + 1

import sys
import string
import operator
from collections import Counter

f = sys.stdin

while True:
    x, y = map(int, f.readline().split())
    if x == y == 0:
        break
    s = [f.readline().split() for _ in range(y)]
    
    dict = {'R':0,'G':1,'B':2}
    for si in s:
        for j in range(len(si)):
            si[j] = dict[si[j]]
    
    print(dfs(0, s, 0))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def paintout(s, color,w,h):
    cnt, pre_color = 0, s[0]

    que = deque([(0, 0)])
    while len(que):
        x, y = que.pop()
        pos = y * w + x
        if 0 <= x < w and 0 <= y < h and s[pos] == pre_color:
            s[pos] = color
            cnt +=1
            que.extend(((x-1,y),(x,y-1),(x+1,y),(x,y+1)))

    return cnt

def dfs(depth, s, pre_cnt, w, h):
    ret = []
    pre_color = s[0]
    
    colors = [0,1,2]
    colors.remove(pre_color)
    
    for color in colors:
        p = s[:]
        cnt = paintout(p,color,w,h)
        if cnt == h * w:
            return depth
        if cnt == pre_cnt:
            return float('inf')
        ret.append(dfs(depth + 1, p, cnt,w,h))

    return min(ret)

import sys
import string
import operator
from collections import Counter

f = sys.stdin

while True:
    x, y = map(int, f.readline().split())
    if x == y == 0:
        break
    s = [f.readline().split() for _ in range(y)]
    
    dict = {'R':0,'G':1,'B':2}
    for si in s:
        for j in range(len(si)):
            si[j] = dict[si[j]]
    s = [y for x in s for y in x]
    
    print(dfs(0, s, 0, x, y))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def paintout(s, color,w,h):
    cnt, pre_color = 0, s[0]

    que = deque([(0, 0)])
    while len(que):
        x, y = que.pop()
        pos = y * w + x
        if 0 <= x < w and 0 <= y < h and s[pos] == pre_color:
            s[pos] = color
            cnt +=1
            que.extend(((x-1,y),(x,y-1),(x+1,y),(x,y+1)))

    return cnt

def dfs(depth, s, pre_cnt, w, h):
    global good
    if good <= depth:
        return float('inf')
    ret = []
    pre_color = s[0]
    
    colors = [0,1,2]
    colors.remove(pre_color)
    
    for color in colors:
        p = s[:]
        cnt = paintout(p,color,w,h)
        if cnt == h * w:
            good = min(good,depth)
            return good
        if cnt == pre_cnt:
            return float('inf')
        ret.append(dfs(depth + 1, p, cnt,w,h))

    return min(ret)

import sys
import string
import operator
from collections import Counter

f = sys.stdin

while True:
    good = float('inf')
    x, y = map(int, f.readline().split())
    if x == y == 0:
        break
    s = [f.readline().split() for _ in range(y)]
    
    dict = {'R':0,'G':1,'B':2}
    for si in s:
        for j in range(len(si)):
            si[j] = dict[si[j]]
    s = [y for x in s for y in x]
    
    print(dfs(0, s, 0, x, y))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def paintout(s, color,w,h):
    cnt, pre_color = 0, s[0]
 
    que = deque([(0, 0)])
    while len(que):
        x, y = que.pop()
        pos = y * w + x
        if s[pos] == pre_color:
            s[pos] = color
            cnt +=1
            if 0 < x:
                que.append((x-1,y))
            if 0 < y:
                que.append((x,y-1))
            if x + 1 < w:
                que.append((x+1,y))
            if y + 1 < h:
                que.append((x,y+1))

    return cnt

def dfs(depth, s, pre_cnt, w, h):
    global good
    if good <= depth:
        return float('inf')
    ret = []
    pre_color = s[0]
     
    colors = [0,1,2]
    colors.remove(pre_color)
     
    for color in colors:
        p = s[:]
        cnt = paintout(p,color,w,h)
        if cnt == pre_cnt:
            return float('inf')
        if cnt == h * w:
            good = min(good,depth)
            return good
        ret.append(dfs(depth + 1, p, cnt,w,h))
 
    return min(ret)

import sys
f = sys.stdin 

while True:
    good = float('inf')
    x, y = map(int, f.readline().split())
    if x == y == 0:
        break
    s = [f.readline().split() for _ in range(y)]
     
    dict = {'R':0,'G':1,'B':2}
    for si in s:
        for j in range(len(si)):
            si[j] = dict[si[j]]
    s = [y for x in s for y in x]
     
    print(dfs(0, s, 0, x, y))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def paintout(s, color,w,h):
    cnt, pre_color = 0, s[0]
 
    que = deque([(0, 0)])
    while len(que):
        x, y = que.popleft()
        pos = y * w + x
        if s[pos] == pre_color:
            s[pos] = color
            cnt +=1
            if x + 1 < w:
                que.append((x+1,y))
            if y + 1 < h:
                que.append((x,y+1))
            if 0 < x:
                que.append((x-1,y))
            if 0 < y:
                que.append((x,y-1))
    return cnt

def bfs(s, w, h):
    que = deque([(s,0,0)])
    while True:
        s,pre_cnt,depth = que.popleft()
        pre_color = s[0]
    
        colors = [0,1,2]
        colors.remove(pre_color)

        for si, color in zip((s,s[:]),colors):
            cnt = paintout(si,color,w,h)
            if cnt == h * w:
                return depth
            if cnt == pre_cnt:
                break
            que.append((si,cnt,depth + 1))

import sys
f = sys.stdin

while True:
    good = float('inf')
    x, y = map(int, f.readline().split())
    if x == y == 0:
        break
    s = [f.readline().split() for _ in range(y)]
     
    dict = {'R':0,'G':1,'B':2}
    for si in s:
        for j in range(len(si)):
            si[j] = dict[si[j]]
    s = [y for x in s for y in x]
     
    print(bfs(s, x, y))

Submission status: Accepted

Solution code:
def paintout_graph(s, g, color):
    cnt, pre_color = 0, s[0]
    que = [0]
    for pos in que:
        if s[pos] == pre_color:
            s[pos] = color
            cnt +=1
            que.extend(g[pos])
    return cnt
def bfs(s, graph):
    que = deque([(s,0,0)])
    while True:
        s,pre_cnt,depth = que.popleft()
        pre_color = s[0]
    
        colors = ['R','G','B']
        colors.remove(pre_color)

        for si, color in zip((s,s[:]),colors):
            cnt = paintout_graph(si,graph,color)
            if cnt == len(si):
                return depth
            if cnt == pre_cnt:
                break
            que.append((si,cnt,depth + 1))
from collections import deque
def paintout_sq(s, color,w,h,x,y):
    neighbor, pre_color = set(), s[y*w+x]

    que = deque([(x, y)])
    while len(que):
        x, y = que.pop()
        pos = y * w + x
        if s[pos] == pre_color:
            s[pos] = color
            if 0 < x:que.append((x-1,y))
            if 0 < y:que.append((x,y-1))
            if x + 1 < w:que.append((x+1,y))
            if y + 1 < h:que.append((x,y+1))
        elif s[pos] != color and isinstance(s[pos], int):
            neighbor.update([s[pos]])

    return neighbor

import sys
f = sys.stdin

while True:
    w, h = map(int, f.readline().split())
    if w == h == 0:
        break
    s = [f.readline().split() for _ in range(h)]
    s = [y for x in s for y in x]
    p = []
    graph = {}
    for y in range(h):
        for x in range(w):
            pos = y*w+x
            if s[pos] in ('R','G','B'):
                k = len(p)
                p.append(s[pos])
                neighbor = paintout_sq(s,k,w,h,x,y)
                neighbor = list(neighbor)
                try:
                    graph[k].expand(neighbor)
                except KeyError:
                    graph[k] = neighbor
                for ni in neighbor:
                    try:
                        graph[ni].append(k)
                    except KeyError:
                        graph[ni] = [k]
    print(bfs(p,graph))