Problem:


真っ暗な部屋

目を覚ますと、A君は真っ暗な部屋の中にいた。
どうやらA君は N 個の部屋から構成されたダンジョンに迷い込んでしまったようだ。
あなたはA君がどの部屋に迷い込んだのかを知ることはできなかったが、幸いにもダンジョンのマップを手に入れることができた。
A君の進むべき道を示し明るい部屋に導こう。

N 個の部屋のうち M 個の部屋が真っ暗な部屋であり、それぞれ D_1, D_2, ..., D_M 番目の部屋が真っ暗な部屋であることが分かっている。
また、全ての部屋からちょうど K 本の一方通行の道が順に並んでおり、i 番目の部屋から出る道はそれぞれ 
v_{i,1}, v_{i,2}, ..., v_{i,K} 番目の部屋に繋がっている。
あなたは、A君に対し今いる部屋から a_1, a_2, ..., a_l 番目の道を順に進ませることができる。
ただし、A君は明るい部屋に到達したらそれ以降の指示は無視する。
あなたは、指示の前後においてA君が今いる部屋の情報を知ることはできないため、A君がどの部屋にいたとしても明るい部屋に辿り着けるような指示列を伝えなければならない。

そのような指示のうち、最も短いものの長さを答えよ。

Constraints

2  ≤  N  ≤  100

1  ≤  M  ≤  min(16, N &minus; 1)

1  ≤  K  ≤  N

1  ≤  D_i  ≤  N

D_i は全て異なる

1  ≤  v_{i, j}  ≤  N

 全ての暗い部屋は少なくとも1つの明るい部屋に到達可能である 

Input Format

入力は以下の形式で標準入力から与えられる。

N M K
D_1 D_2 ... D_M
v_{1,1} v_{1,2} ... v_{1,K}
v_{2,1} v_{2,2} ... v_{2,K}
...
v_{N,1} v_{N,2} ... v_{N,K}

Output Format

答えを一行に出力せよ。

Sample Input 1

4 2 2
1 2
2 4
3 1
4 2
1 3

Sample Output 1

2

 

1, 1 という指示を出すと

A君の初期位置が部屋1である場合、2つ目の移動で部屋3に到達する

A君の初期位置が部屋2である場合、1つ目の移動で部屋3に到達する

Sample Input 2

3 2 2
1 2
2 3
1 2
2 1

Sample Output 2

3

 

2, 1, 2 という指示を出すと

A君の初期位置が部屋1である場合、1つ目の移動で部屋3に到達する

A君の初期位置が部屋2である場合、3つ目の移動で部屋3に到達する

Sample Input 3

6 3 3
1 2 3
4 1 1
2 5 2
3 3 6
4 4 4
5 5 5
6 6 6

Sample Output 3

3

 

非連結であるケースや、自己辺、多重辺があるケースに気をつけよう



Sample input:
4 2 2
1 2
2 4
3 1
4 2
1 3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

def main():
    n,m,k = map(int, sys.stdin.readline().split())
    darks = list(map(lambda x: x-1, map(int, sys.stdin.readline().split())))
    edges = []
    for i in range(n):
        edges.append( list(map(lambda x: x-1, map(int, sys.stdin.readline().split()))) )

    q = queue.Queue()
    dp = {}

    dp[ (1 << m) - 1 ] = 0
    q.put( ((1 << m) - 1, 0) )

    ans = -1
    while not q.empty():
        state,cost = q.get()
        for i in range(k):
            next_state = 0
            for j in range(m):
                if not (state & (1 << j)):
                    continue
                #print("darks[{}]:{}\ti:{}\tedges[][]:{}".format(j, darks[j], i, edges[darks[j]][i]))
                if edges[darks[j]][i] in darks:
                    next_state |= (1 << darks.index(edges[darks[j]][i]))
            #print(bin(next_state))
            if next_state == 0:
                ans = cost + 1
                break
            if next_state not in dp:
                dp[next_state] = cost + 1
                q.put( (next_state, cost + 1) )
        if ans != -1:
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 = 10**9+7
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():
    n,m,k = LI()
    d = LI()
    v = [LI() for _ in range(n)]
    u = set()
    ds = set(d)
    u.add(tuple(d))
    q = [(tuple(d), 1)]
    while q:
        qd, qk = q.pop(0)
        for vi in range(k):
            t = set()
            for di in qd:
                t.add(v[di-1][vi])
            t &= ds
            tt = tuple(t)
            if tt in u:
                continue
            if len(tt) == 0:
                return qk
            u.add(tt)
            q.append((tt,qk+1))

    return -1



print(main())

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 = 10**9+7
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():
    n,m,k = LI()
    d = LI_()
    v = [LI_() for _ in range(n)]
    dd = collections.defaultdict(lambda: None)
    for i in range(m):
        dd[d[i]] = i
    vv = []
    for c in d:
        vv.append([dd[v[c][i]] for i in range(k)])
    vvv = [[vv[i][j] for i in range(m)] for j in range(k)]
    u = set()
    m2 = 2**m
    u.add(m2-1)
    q = [(m2-1, 1)]
    ii = [2**_ for _ in range(m)]
    # print('vv',vv)
    while q:
        qd, qk = q.pop(0)
        # print('q', qd,qk)
        qdi = [di for di in range(m) if qd & ii[di]]
        for vi in range(k):
            t = 0
            vvi = vvv[vi]
            for di in qdi:
                if not vvi[di] is None:
                    t |= ii[vvi[di]]
            # print('vit',vi,t)
            if t in u:
                continue
            if t == 0:
                return qk
            u.add(t)
            q.append((t,qk+1))

    return -1



print(main())

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 = 10**9+7
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():
    n,m,k = LI()
    d = LI_()
    v = [LI_() for _ in range(n)]
    dd = collections.defaultdict(lambda: None)
    for i in range(m):
        dd[d[i]] = i
    ii = [2**_ for _ in range(m)]
    vv = [[ii[dd[v[c][i]]] if not dd[v[c][i]] is None else 0  for c in d] for i in range(k)]
    m2 = 2**m
    u = [None] * m2
    u[-1] = 1
    q = [m2-1]
    r = 0
    while q:
        r += 1
        nq = []
        for qd in q:
            qdi = [di for di in range(m) if qd & ii[di]]
            for vi in range(k):
                t = 0
                vvi = vv[vi]
                for di in qdi:
                    t |= vvi[di]
                if not u[t] is None:
                    continue
                if t == 0:
                    return r
                u[t] = 1
                nq.append(t)
        q = nq

    return -1



print(main())

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    n,m,k = map(int, input().split())
    d = list(map(int, input().split()))
    l = [-1] * n
    for i in range(m):
      l[d[i]-1] = i
    A = [list(map(int, input().split())) for _ in range(n)]
    a = [[l[A[i-1][j] - 1] if l[A[i-1][j] - 1] != -1 else None for i in d] for j in range(k)]
    c = [-1] * (1 << m)
    c[(1 << m) - 1] = 0
    D = [1 << i for i in range(m+1)]
    x = [-1] * m
    q = defaultdict(int)
    Range = range(m)
    K = 0
    q[0] = -1
    R = 1
    while 1:
        mask = q[K]
        K += 1
        score = c[mask] + 1
        x = [i for i in Range if mask & D[i]]
        for ai in a:
            tmp = 0
            for j in x:
                aji = ai[j] 
                if aji != None:
                	tmp |= D[aji]
            if c[tmp] == -1:
                c[tmp] = score
                q[R] = tmp
                R += 1
                if tmp == 0:
                    print(score)
                    return
if __name__ == "__main__":
    main()