Problem:


Problem B: 平安京ウォーキング

平安京は、道が格子状になっている町として知られている。

平安京に住んでいるねこのホクサイは、パトロールのために毎日自宅から町はずれの秘密の場所まで行かなければならない。しかし、毎日同じ道を通るのは飽きるし、後を付けられる危険もあるので、ホクサイはできるだけ毎日異なる経路を使いたい。その一方で、ホクサイは面倒臭がりなので、目的地から遠ざかるような道は通りたくない。

平安京のあちこちの道にはマタタビが落ちていて、ホクサイはマタタビが落ちている道を通ることができない。そのような道を通るとめろめろになってしまうからである。幸いなことに、交差点にはマタタビは落ちていない。

ホクサイは、自宅から秘密の場所までの可能な経路の数を知りたい。ここで、ホクサイの自宅は (0, 0) にあり、秘密の場所は(gx, gy)にある。道は x = i (i は整数), y = j (j は整数) に格子状に敷かれている。

Input

入力の1行目には、秘密の場所の座標 (gx, gy) が与えられる。これらはいずれも1以上15以下の整数で、空白1個で区切られて与えられる。 2行目にはマタタビが落ちている区間の数 p (0 ≤ p ≤ 100) が与えられ、続くp行にはマタタビが落ちている区間が1行に1区間ずつ与えられる。 p個の区間は互いに異なる。 1区間は x1 y1 x2 y2 の形で表され、(x1, y1) と (x2, y2) を端点とする、x軸またはy軸に平行な長さ1の線分である。 x1, x2 は [0, gx] の範囲にあり、y1, y2 は [0, gy] の範囲にある。

Output

可能な経路の数を出力せよ。可能な経路が1つもない場合は "Miserable Hokusai!" と1行に出力せよ。

Notes on Submission

上記形式で複数のデータセットが与えられます。入力データの 1 行目にデータセットの数が与えられます。各データセットに対する出力を上記形式で順番に出力するプログラムを作成して下さい。

Sample Input

4
2 2
0
1 1
2
0 0 0 1
0 0 1 0
4 3
4
1 0 0 0
3 3 4 3
4 1 4 0
0 2 0 3
15 15
0

Output for the Sample Input

6
Miserable Hokusai!
5
155117520



Sample input:
4
2 2
0
1 1
2
0 0 0 1
0 0 1 0
4 3
4
1 0 0 0
3 3 4 3
4 1 4 0
0 2 0 3
15 15
0


Sample output:
6
Miserable Hokusai!
5
155117520

Submission status: Wrong Answer

Solution code:
L = int(input().strip())
for _ in range(0,L):
    gx,gy = map(int,input().strip().split(" "))
    heiankyo = [[0 for j in range(0,gx+1)] for i in range(0,gy+1)]
    heiankyo[0][0] = 1
    P = int(input())
    matatabi = []
    for p in range(P):
        x1,y1,x2,y2 = map(int,input().strip().split(" "))
        l = [[x1,y1],[x2,y2]]    
        l.sort()
        matatabi.append(l)
    for i in range(1,gy+1):
        if not [[i-1,0],[i,0]] in matatabi:
            heiankyo[i][0] = heiankyo[i-1][0]
    for j in range(1,gx+1):
        if not [[0,j-1],[0,j]] in matatabi:
            heiankyo[0][j] = heiankyo[0][j-1]
    for i in range(1,gy+1):
        for j in range(1,gx+1):
            if not [[i-1,j],[i,j]] in matatabi:
                heiankyo[i][j] = heiankyo[i][j] + heiankyo[i-1][j]
            if not [[i,j-1],[i,j]] in matatabi:
                heiankyo[i][j] = heiankyo[i][j] + heiankyo[i][j-1]
    if heiankyo[gy][gx] == 0:
        print("Miserable Hokusai!")
    else:
        print(heiankyo[gy][gx])

Submission status: Wrong Answer

Solution code:
trial = int(input())

for t in range(trial):
    targ = [int(n) for n in input().split(' ')]
    root = [[0 for n in range(targ[0] + 1)] for m in range(targ[1] + 1)]
    matanum = int(input())
    for m in range(matanum):
        matax,matay,secx,secy = (int(n) for n in input().split(' '))
        if matax == secx:
            root[max(matay,secy)][matax] = 'y'
        else:
            root[matay][max(secx,matax)] = 'x'
    root[0][0] = 1
    for yaxis in range(targ[1] + 1):
        for xaxis in range(targ[0] + 1):
            if xaxis == 0:
                if root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = 0
                else:
                    root[yaxis][xaxis] = 1
            elif yaxis == 0:
                if root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = 0
                else:
                    root[yaxis][xaxis] = root[yaxis][xaxis-1]
            else:
                if root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = root[yaxis][xaxis - 1]
                elif root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis]
                else:
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis] + root[yaxis][xaxis - 1]

if root[targ[1]][targ[0]] == 0:
    print("Miserable Hokusai!")
else:
    print(root[targ[1]][targ[0]])

Submission status: Wrong Answer

Solution code:
trial = int(input())

for t in range(trial):
    targ = [int(n) for n in input().split(' ')]
    root = [[0 for n in range(targ[0] + 1)] for m in range(targ[1] + 1)]
    matanum = int(input())
    for m in range(matanum):
        matax,matay,secx,secy = (int(n) for n in input().split(' '))
        if matax == secx:
            root[max(matay,secy)][matax] = 'y'
        else:
            root[matay][max(secx,matax)] = 'x'
    root[0][0] = 1
    for yaxis in range(targ[1] + 1):
        for xaxis in range(targ[0] + 1):
            if xaxis == 0:
                if root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = 0
                else:
                    root[yaxis][xaxis] = 1
            elif yaxis == 0:
                if root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = 0
                else:
                    root[yaxis][xaxis] = root[yaxis][xaxis-1]
            else:
                if root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = root[yaxis][xaxis - 1]
                elif root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis]
                else:
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis] + root[yaxis][xaxis - 1]
    if root[targ[1]][targ[0]] == 0:
        print("Miserable Hokusai!")
    else:
        print(root[targ[1]][targ[0]])

Submission status: Wrong Answer

Solution code:
trial = int(input())

for t in range(trial):
    targ = [int(n) for n in input().split(' ')]
    root = [[0 for n in range(targ[0] + 1)] for m in range(targ[1] + 1)]
    matanum = int(input())
    for m in range(matanum):
        matax,matay,secx,secy = (int(n) for n in input().split(' '))
        if matax == secx:
            root[max(matay,secy)][matax] = 'y'
        else:
            root[matay][max(secx,matax)] = 'x'
    root[0][0] = 1
    for yaxis in range(targ[1] + 1):
        for xaxis in range(targ[0] + 1):
            if xaxis == 0:
                if root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = 0
                else:
                    if yaxis == 0:
                        root[0][0] = 1
                    else:
                        root[yaxis][xaxis] = root[yaxis- 1][xaxis]
            elif yaxis == 0:
                if root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = 0
                else:
                    root[yaxis][xaxis] = root[yaxis][xaxis-1]
            else:
                if root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = root[yaxis][xaxis - 1]
                elif root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis]
                else:
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis] + root[yaxis][xaxis - 1]
    if root[targ[1]][targ[0]] == 0:
        print("Miserable Hokusai!")
    else:
        print(root[targ[1]][targ[0]])

Submission status: Wrong Answer

Solution code:
trial = int(input())

for t in range(trial):
    targ = [int(n) for n in input().split(' ')]
    root = [[0 for n in range(targ[0] + 1)] for m in range(targ[1] + 1)]
    matanum = int(input())
    for m in range(matanum):
        matax,matay,secx,secy = (int(n) for n in input().split(' '))
        if matax == secx:
            root[max(matay,secy)][matax] = 'y'
        else:
            root[matay][max(secx,matax)] = 'x'
    for yaxis in range(targ[1] + 1):
        for xaxis in range(targ[0] + 1):
            if xaxis == 0:
                if root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = 0
                else:
                    if yaxis == 0:
                        root[0][0] = 1
                    else:
                        root[yaxis][xaxis] = root[yaxis- 1][xaxis]
            elif yaxis == 0:
                if root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = 0
                else:
                    root[yaxis][xaxis] = root[yaxis][xaxis-1]
            else:
                if root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = root[yaxis][xaxis - 1]
                elif root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis]
                else:
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis] + root[yaxis][xaxis - 1]
    if root[targ[1]][targ[0]] == 0:
        print("Miserable Hokusai!")
    else:
        print(root[targ[1]][targ[0]])

Submission status: Wrong Answer

Solution code:
for _ in range(int(input())):
    x, y = map(int, input().split())
    m = set()
    for _ in range(int(input())):m.add(tuple(map(int, input().split())))
    q = {(0,0):1}
    for _ in range(x + y):
        nq = {}
        for i in q:
            if (i[0], i[1], i[0] + 1, i[1]) not in m and i[0] + 1 <= x:
                if (i[0] + 1, i[1]) in nq:nq[(i[0] + 1, i[1])] += q[i]
                else:nq[(i[0] + 1, i[1])] = q[i]
            if (i[0], i[1], i[0], i[1] + 1) not in m and i[1] + 1 <= y:
                if (i[0], i[1] + 1) in nq:nq[(i[0], i[1] + 1)] += q[i]
                else:nq[(i[0], i[1] + 1)] = q[i]
        q = nq
    if nq == {}:print("Miserable Hokusai!")
    else:print(q[x, y])

Submission status: Wrong Answer

Solution code:
for _ in range(int(input())):
    x, y = map(int, input().split())
    m = set()
    for _ in range(int(input())):m.add(tuple(map(int, input().split())))
    q = {(0,0):1}
    for _ in range(x + y):
        nq = {}
        for i in q:
            if (i[0], i[1], i[0] + 1, i[1]) not in m and (i[0] + 1, i[1], i[0], i[1]) not in m and i[0] + 1 <= x:
                if (i[0] + 1, i[1]) in nq:nq[(i[0] + 1, i[1])] += q[i]
                else:nq[(i[0] + 1, i[1])] = q[i]
            if (i[0], i[1], i[0], i[1] + 1) not in m and (i[0], i[1] + 1, i[0], i[1]) not in m and i[1] + 1 <= y:
                if (i[0], i[1] + 1) in nq:nq[(i[0], i[1] + 1)] += q[i]
                else:nq[(i[0], i[1] + 1)] = q[i]

Submission status: Wrong Answer

Solution code:
for _ in xrange(input()):
    gx, gy = map(int, raw_input().split())
    mttb = [[False] * (gx + 2) for _ in xrange(gy + 2)]
    dp = [[0] * (gx + 2) for _ in xrange(gy + 2)]
    p = [map(int, raw_input().split()) for _ in xrange(input())]
    for x1, y1, x2, y2 in p:
        x1, x2 = (x1, x2) if x1 < x2 else (x2, x1)
        y1, y2 = (y1, y2) if y1 < y2 else (y2, y1)
        for y in xrange(y1, y2 + 1):
            for x in xrange(x1, x2 + 1):
                mttb[y][x] = True
    dp[0][0] = 1
    for y in xrange(gy + 1):
        for x in xrange(gx + 1):            
            if not(mttb[y - 1][x] and mttb[y][x]):
                dp[y][x] += dp[y - 1][x]
            if not(mttb[y][x - 1] and mttb[y][x]):
                dp[y][x] += dp[y][x - 1]
    print "Miserable Hokusai!" if dp[gy][gx] == 0 else dp[gy][gx]

Submission status: Accepted

Solution code:
n = int(input())
for i in range(n):
    a,b = map(int, input().split())
    coor = [[0for i in range(b+1)]for i in range(a+1)]
    p = int(input())
    prob = {}
    for k in range(p):
        z,x,c,v = map(int, input().split())
        if (z == c):
            r = max(x,v)
            if ((z,r) in prob.keys()):  ## list는 dictionary의 key가 안되지만 tuple은 가능
                prob[(z,r)] = 'xy'      ## (tuple의 불변성 때문인걸로 기억남)
            else:
                prob[(z,r)] = 'y'
        if (x == v):
            r = max(z,c)
            if ((r,x) in prob.keys()):
                prob[(r,x)] = 'xy'
            else:
                prob[(r,x)] = 'x'
    for k in range(a+1):
        for l in range(b+1):
            if (p == 0):
                if (k == 0 or l == 0):
                    coor[k][l] = 1
                else:
                    coor[k][l] = coor[k-1][l] + coor[k][l-1]   
            elif (k == 0 and l == 0):
                coor[0][0] = 1
            elif (k == 0):
                if ((k,l) in prob.keys()):
                    coor[0][l] = 0
                else:
                    coor[0][l] = coor[0][l-1]
            elif (l == 0):
                if ((k,l) in prob.keys()):
                    coor[k][0] = 0
                else:
                    coor[k][0] = coor[k-1][0]
            elif ((k,l) in prob.keys() and prob[(k,l)] == 'x'):
                coor[k][l] = coor[k][l-1]
            elif ((k,l) in prob.keys() and prob[(k,l)] == 'y'):
                coor[k][l] = coor[k-1][l]
            elif ((k,l) in prob.keys() and prob[(k,l)] == 'xy'):
                coor[k][l] = 0
            else:
                coor[k][l] = coor[k-1][l] + coor[k][l-1]
    co = coor[-1][-1]
    if (co == 0):
        print('Miserable Hokusai!')
    else:
        print(co)

Submission status: Accepted

Solution code:
L = int(input().strip())
for _ in range(0,L):
    gx,gy = map(int,input().strip().split(" "))
    heiankyo = [[0 for j in range(0,gx+1)] for i in range(0,gy+1)]
    heiankyo[0][0] = 1
    P = int(input())
    matatabi = []
    for p in range(P):
        x1,y1,x2,y2 = map(int,input().strip().split(" "))
        l = [[y1,x1],[y2,x2]]    
        l.sort()
        matatabi.append(l)
    for i in range(1,gy+1):
        if not [[i-1,0],[i,0]] in matatabi:
            heiankyo[i][0] = heiankyo[i-1][0]
    for j in range(1,gx+1):
        if not [[0,j-1],[0,j]] in matatabi:
            heiankyo[0][j] = heiankyo[0][j-1]
    for i in range(1,gy+1):
        for j in range(1,gx+1):
            if not [[i-1,j],[i,j]] in matatabi:
                heiankyo[i][j] = heiankyo[i][j] + heiankyo[i-1][j]
            if not [[i,j-1],[i,j]] in matatabi:
                heiankyo[i][j] = heiankyo[i][j] + heiankyo[i][j-1]
    if heiankyo[gy][gx] == 0:
        print("Miserable Hokusai!")
    else:
        print(heiankyo[gy][gx])

Submission status: Accepted

Solution code:
t = int(input())
for _ in range(t):
  gx, gy = map(int, input().split())
  p = int(input())
  right_stop = set()
  down_stop = set()
  
  for _ in range(p):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
      down_stop.add((x1 + 1, min(y1, y2) + 1))
    if y1 == y2:
      right_stop.add((min(x1, x2) + 1, y1 + 1))
  
  dp = [[0] * (gx + 2) for _ in range(gy + 2)]
  dp[1][1] = 1
  for y in range(1, gy + 2):
    for x in range(1, gx + 2):
      if (x - 1, y) not in right_stop:
        dp[y][x] += dp[y][x - 1]
      if (x, y - 1) not in down_stop:
        dp[y][x] += dp[y - 1][x]
  if dp[gy + 1][gx + 1] > 0:
    print(dp[gy + 1][gx + 1])
  else:
    print("Miserable Hokusai!")

Submission status: Accepted

Solution code:
trial = int(input())

for t in range(trial):
    targ = [int(n) for n in input().split(' ')]
    root = [[0 for n in range(targ[0] + 1)] for m in range(targ[1] + 1)]
    matanum = int(input())
    for m in range(matanum):
        matax,matay,secx,secy = (int(n) for n in input().split(' '))
        if matax == secx:
            if root[max(matay,secy)][matax] == 'x':
                root[max(matay,secy)][matax] = 'xy'
            else:
                root[max(matay,secy)][matax] = 'y'
        else:
            if root[matay][max(matax,secx)] == 'y':
                root[matay][max(matax,secx)] = 'xy'
            else:
                root[matay][max(matax,secx)] = 'x'
    for yaxis in range(targ[1] + 1):
        for xaxis in range(targ[0] + 1):
            if xaxis == 0:
                if root[yaxis][xaxis] == 'y' or root[yaxis][xaxis] == 'xy':
                    root[yaxis][xaxis] = 0
                else:
                    if yaxis == 0:
                        root[0][0] = 1
                    else:
                        root[yaxis][xaxis] = root[yaxis- 1][xaxis]
            elif yaxis == 0:
                if root[yaxis][xaxis] == 'x' or root[yaxis][xaxis] == 'xy':
                    root[yaxis][xaxis] = 0
                else:
                    root[yaxis][xaxis] = root[yaxis][xaxis-1]
            else:
                if root[yaxis][xaxis] == 'xy':
                    root[yaxis][xaxis] = 0
                elif root[yaxis][xaxis] == 'y':
                    root[yaxis][xaxis] = root[yaxis][xaxis - 1]
                elif root[yaxis][xaxis] == 'x':
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis]
                else:
                    root[yaxis][xaxis] = root[yaxis - 1][xaxis] + root[yaxis][xaxis - 1]
    if root[targ[1]][targ[0]] == 0:
        print("Miserable Hokusai!")
    else:
        print(root[targ[1]][targ[0]])

Submission status: Accepted

Solution code:
q=int(raw_input())
for _ in xrange(q):
    gx,gy=map(int,raw_input().split())
    route=[[0]*(gy+1) for i in xrange(gx+1)]
    route[0][0]=1
    p=int(raw_input())
    ps=[]
    for i in xrange(p):
        x1,y1,x2,y2=map(int,raw_input().split())
        ps.append((x1,y1,x2,y2))
        ps.append((x2,y2,x1,y1))
    for i in xrange(gx+1):
        for j in xrange(gy+1):
            if i+1<=gx and not (i,j,i+1,j) in ps:
                route[i+1][j] += route[i][j]
            if j+1<=gy and not (i,j,i,j+1) in ps:
                route[i][j+1] += route[i][j]
    if route[gx][gy]==0: print "Miserable Hokusai!"
    else: print route[gx][gy]

Submission status: Accepted

Solution code:
t=int(input())

#mapH[j][i]=(i,j)

for repeet in range(t):
        actinidia_tate=[]
        actinidia_yoko=[]
        gx,gy=[int(i) for i in input().split(" ")]

        mapH=[[0 for i in range(gx+1)] for j in range(gy+1)]
        mapH[0][0]=1
        p=int(input())
        for i in range(p):
                x1,y1,x2,y2=[int(j) for j in input().split(" ")]
                if x1==x2:
                        actinidia_tate.append([x1,max(y1,y2)])
                else:
                        actinidia_yoko.append([max(x1,x2),y1])
	
        for i in range(1,gx+1):
                try:
                        actinidia_yoko.remove([i,0])
                except:
                        mapH[0][i]+=mapH[0][i-1]
        for j in range(1,gy+1):
                try:
                        actinidia_tate.remove([0,j])
                except:
                        mapH[j][0]+=mapH[j-1][0]
	
        for i in range(1,gx+1):
                for j in range(1,gy+1):
                        try:
                                actinidia_yoko.remove([i,j])
                        except:
                                mapH[j][i]+=mapH[j][i-1]
                        try:
                                actinidia_tate.remove([i,j])
                        except:
                                mapH[j][i]+=mapH[j-1][i]


        if mapH[-1][-1]==0:
                print("Miserable Hokusai!")

        else:
                print(mapH[-1][-1])

Submission status: Accepted

Solution code:
n = int(input())
for i in range(n):
    x, y = map(int, input().split())
    t = [[0 for i in range(x + 1)] for j in range(y + 1)]
    p = int(input())
    if p>0:
        for j in range(p):
            x1, y1, x2, y2 = map(int, input().split())
            if x1 == x2:
                for k in range(min(y1, y2)+1, max(y1, y2)+1):
                    if t[k][x1] == 'x':
                        t[k][x1] = 'xy'
                    else:
                        t[k][x1] = 'y'
            if y1 == y2:
                for k in range(min(x1, x2)+1, max(x1, x2)+1):
                    if t[y1][k] == 'y':
                        t[y1][k] = 'xy'
                    else:
                        t[y1][k] = 'x'
    for i in range(x + 1):
        for j in range(y + 1):
            if i == 0 and j ==0:
                t[j][i] = 1
            elif t[j][i] == 'xy':
                t[j][i] = 0
            elif t[j][i] == 'x':
                if j == 0:
                    t[j][i] =0
                else:
                    t[j][i] = t[j-1][i]
            elif t[j][i] == 'y':
                if i == 0:
                    t[j][i] = 0
                else:
                    t[j][i] = t[j][i-1]
            else:
                #print(i,j)
                if i != 0 and j != 0:
                    t[j][i] =  t[j][i-1] + t[j-1][i]
                if i == 0:
                    t[j][i] = t[j-1][i]
                if j == 0:
                    t[j][i] = t[j][i-1]
                #print(t)
    # print(t)
    if t[y][x] == 0:
        print('Miserable Hokusai!')
    else:
        print(t[y][x])

Submission status: Accepted

Solution code:
def Heian():
    g = input().split()

    x = int(g[0])
    y = int(g[1])

    #= int(input().strip())

    M=int(input())
    a = []
    for i in range(M):
        a.append(list(map(int, input().split())))

    #Process Vert and Horiz
    Vert=[[True for i2 in range(x+1)]for i1 in range(y+1)]
    Horiz=[[True for i2 in range(x+1)]for i1 in range(y+1)]


    for i in range(x+1):
        Vert[0][i]=False
    for i in range(y+1):
        Horiz[i][0]=False

    for i in range(M):
        x1=a[i][0]
        x2=a[i][2]
        y1=a[i][1]
        y2=a[i][3]
        if x1==x2:
            Vert[max(y1,y2)][x1]=False
        if y1==y2:
            Horiz[y1][max(x1,x2)]=False

    Txy=[[0 for i2 in range(x+1)]for i1 in range(y+1)]
    for i in range(x+1):
        for j in range(y+1):
            if Vert[j][i]==False and Horiz[j][i]==False:
                if i==0 and j==0:
                    Txy[i][j]=1
                else:
                    Txy[j][i]=0
            elif Vert[j][i]==False:
                if i==0:
                    Txy[j][i]=0
                else:
                    Txy[j][i]=Txy[j][i-1]
            elif Horiz[j][i]==False:
                if j==0:
                    Txy[j][i]=0
                else:
                    Txy[j][i]=Txy[j-1][i]
            else:
                Txy[j][i]=Txy[j-1][i]+Txy[j][i-1]

    if Txy[y][x]==0:
        print("Miserable Hokusai!")
    else:
        print(Txy[y][x])


N = int(input())

for i in range(N):
    Heian()

Submission status: Accepted

Solution code:
for _ in range(int(input())):
    G = list(map(int, input().split()))
    yokomata = []
    tatemata = []
    for i in range(int(input())):
        m = (list(map(int, input().split())))
        if m[1] == m[3]:
            yokomata.append([max(m[0], m[2]), m[1]])
        else:
            tatemata.append([m[0], max(m[1], m[3])])
    matrix = [[0 for i in range(G[0]+1)] for j in range(G[1]+1)]
    matrix[0][0] = 1
    for i in range(1, G[0]+1):
        if [i, 0] in yokomata:
            continue
        else:
            matrix[0][i] = matrix[0][i-1]
    for j in range(1, G[1]+1):
        if [0, j] in tatemata:
            continue
        else:
            matrix[j][0] = matrix[j-1][0]
    for j in range(1, G[1] + 1):
        for i in range(1, G[0] + 1):
            if [i, j] in yokomata and [i, j] in tatemata:
                matrix[j][i] = 0
            elif [i, j] in yokomata:
                matrix[j][i] = matrix[j-1][i]
            elif [i, j] in tatemata:
                matrix[j][i] = matrix[j][i-1]
            else:
                matrix[j][i] = matrix[j-1][i] + matrix[j][i-1]
    if matrix[G[1]][G[0]] == 0:
        print("Miserable Hokusai!")
    else:
        print(matrix[G[1]][G[0]])

Submission status: Accepted

Solution code:
n = int(input())

ans = []

for _ in range(n):
    gx,gy = map(int,input().split())
    m = [[0 for i_ in range(gy+1)] for j_ in range(gx+1)]
    mat_num = int(input())
    mat_h = [[0 for i_ in range(gy+1)] for j_ in range(gx+1)]
    mat_v = [[0 for i_ in range(gy+1)] for j_ in range(gx+1)]
    ifm = [[0 for i_ in range(gy+1)] for j_ in range(gx+1)]
    for __ in range(mat_num):
        x1,y1,x2,y2 = map(int,input().split())
        if x1 == x2:
            mat_h[x1][max(y1,y2)] = 1
        else:
            mat_v[max(x1,x2)][y1] = 1
    queue = [(0,0)]
    while queue:
        x,y = queue.pop(0)
        if ifm[x][y] == 0:
            if x == 0:
                if y == 0:
                    m[x][y] = 1
                else:
                    if mat_h[x][y] == 0:
                        m[x][y] += m[x][y-1]
                    else:
                        pass
            else:
                if y == 0:
                    if mat_v[x][y] == 0:
                        m[x][y] += m[x-1][y]
                    else:
                        pass
                else:
                    if mat_v[x][y] == 0:
                        m[x][y] += m[x-1][y]
                    if mat_h[x][y] == 0:
                        m[x][y] += m[x][y-1]
            ifm[x][y] = 1
            if x < gx:
                queue.append((x+1,y))
            if y < gy:
                queue.append((x,y+1))
        else:
            pass
    ans.append(m[gx][gy])

for x in ans:
    if x == 0:
        print('Miserable Hokusai!')
    else:
        print(x)

Submission status: Accepted

Solution code:
for _ in range(int(input())):
    x, y = map(int, input().split())
    m = set()
    for _ in range(int(input())):m.add(tuple(map(int, input().split())))
    q = {(0,0):1}
    for _ in range(x + y):
        nq = {}
        for i in q:
            if (i[0], i[1], i[0] + 1, i[1]) not in m and (i[0] + 1, i[1], i[0], i[1]) not in m and i[0] + 1 <= x:
                if (i[0] + 1, i[1]) in nq:nq[(i[0] + 1, i[1])] += q[i]
                else:nq[(i[0] + 1, i[1])] = q[i]
            if (i[0], i[1], i[0], i[1] + 1) not in m and (i[0], i[1] + 1, i[0], i[1]) not in m and i[1] + 1 <= y:
                if (i[0], i[1] + 1) in nq:nq[(i[0], i[1] + 1)] += q[i]
                else:nq[(i[0], i[1] + 1)] = q[i]
        q = nq
    if nq == {}:print("Miserable Hokusai!")
    else:print(q[(x, y)])

Submission status: Accepted

Solution code:
for i in range(input()):
    gx,gy=map(int,raw_input().split())
    L=[[0]*(gx+1) for i in range(gy+1)]
    p=input()
    mata=[map(int,raw_input().split()) for i in range(p)]
    mata=set(tuple(sorted(((i,j),(k,l)))) for i,j,k,l in mata)
    L[0][0]=1
    for i in range(gy+1):
        for j in range(gx+1):
            if ((j,i-1),(j,i)) in mata and ((j-1,i),(j,i)) in mata:
                L[i][j]=0
            elif ((j,i-1),(j,i)) in mata:
                L[i][j]=L[i][j-1]
            elif ((j-1,i),(j,i)) in mata:
                L[i][j]=L[i-1][j]
            elif i==0 and j==0:
                pass
            elif i==0:
                L[i][j]=L[i][j-1]
            elif j==0:
                L[i][j]=L[i-1][j]
            else:
                L[i][j]=L[i-1][j]+L[i][j-1]
    print L[gy][gx] if L[gy][gx]!=0 else "Miserable Hokusai!"

Submission status: Accepted

Solution code:
def swap(x1, y1, x2, y2):
    x1, x2 = (x1, x2) if x1 < x2 else (x2, x1)
    y1, y2 = (y1, y2) if y1 < y2 else (y2, y1)
    return (x1, y1, x2, y2)
    
for _ in xrange(input()):
    gx, gy = map(int, raw_input().split())
    dp = [[0] * (gx + 2) for _ in xrange(gy + 2)]
    mttb = [swap(*map(int, raw_input().split())) for _ in xrange(input())]
    dp[0][0] = 1
    for y in xrange(gy + 1):
        for x in xrange(gx + 1):            
            if not (x - 1, y, x, y) in mttb:
                dp[y][x] += dp[y][x - 1]
            if not (x, y - 1, x, y) in mttb:
                dp[y][x] += dp[y - 1][x]
    print "Miserable Hokusai!" if dp[gy][gx] == 0 else dp[gy][gx]

Submission status: Accepted

Solution code:
N=int(input())

for n in range(N):
    gx,gy =map(int,input().split())
    T=[[0 for i in range(gy+1)] for j in range(gx+1)]
    left=[[0 for i in range(gy+1)] for j in range(gx+1)]
    upper=[[0 for i in range(gy+1)] for j in range(gx+1)]
    p=int(input())
   
    for i in range(p):
        x1,y1,x2,y2=map(int,input().split())
        if x1==x2:
            upper[x1][max(y1,y2)]=1
        if y1==y2:
            left[max(x1,x2)][y1]=1

    for i in range(gx+1):

        for j in range(gy+1):
            if i==0 and j==0:
                T[i][j]=1
                continue

            if i==0 and j>=1 and upper[i][j]==0 and left[i][j]==0:
                T[i][j]=T[i][j-1]
                continue

            if i>=1 and j==0 and upper[i][j]==0 and left[i][j]==0:
                T[i][j]=T[i-1][j]
                continue
                
            if left[i][j]==1 and upper[i][j]==1:
                    T[i][j]=0
            elif left[i][j]==0 and upper[i][j]==1:
                    T[i][j]=T[i-1][j]
            elif left[i][j]==1 and upper[i][j]==0:
                    T[i][j]=T[i][j-1]
            else:
                T[i][j]=T[i-1][j]+T[i][j-1]

    if T[gx][gy]==0:
        print("Miserable Hokusai!")
    else:
        print(T[gx][gy])

Submission status: Accepted

Solution code:
N=int(input())
for n in range(N):
    gx,gy=map(int,input().split())
    T=[[0 for i in range(gy+1)] for j in range(gx+1)]
    left=[[0 for i in range(gy+1)] for j in range(gx+1)]
    upper=[[0 for i in range(gy+1)] for j in range(gx+1)]
    p=int(input())
    
    for i in range(p):       

        x1,y1,x2,y2=map(int,input().split())

        if x1==x2:

            upper[x1][max(y1,y2)]=1

        if y1==y2:

            left[max(x1,x2)][y1]=1

    for i in range(gx+1):

        for j in range(gy+1):

            if i==0:

                left[i][j]=1

            if j==0:

                upper[i][j]=1
                
    for i in range(gx+1):

        for j in range(gy+1):

            if i==0 and j==0:

                T[i][j]=1

            else:   

                if left[i][j]==1 and upper[i][j]==1:

                    T[i][j]=0

                elif left[i][j]==0 and upper[i][j]==1:

                    T[i][j]=T[i-1][j]

                elif left[i][j]==1 and upper[i][j]==0:

                    T[i][j]=T[i][j-1]

                else:

                    T[i][j]=T[i-1][j]+T[i][j-1]

    
    if T[gx][gy]==0:

        print("Miserable Hokusai!")

    else:

        print(T[gx][gy])

Submission status: Accepted

Solution code:
N=int(input())



for n in range(N):

    gx,gy =map(int,input().split())

    T=[[0 for i in range(gy+1)] for j in range(gx+1)]

    left=[[0 for i in range(gy+1)] for j in range(gx+1)]

    upper=[[0 for i in range(gy+1)] for j in range(gx+1)]

    p=int(input())

   

    for i in range(p):

        x1,y1,x2,y2=map(int,input().split())

        if x1==x2:

            upper[x1][max(y1,y2)]=1

        if y1==y2:

            left[max(x1,x2)][y1]=1



    for i in range(gx+1):



        for j in range(gy+1):

            if i==0 and j==0:

                T[i][j]=1

                continue



            if i==0 and j>=1 and upper[i][j]==0 and left[i][j]==0:

                T[i][j]=T[i][j-1]

                continue



            if i>=1 and j==0 and upper[i][j]==0 and left[i][j]==0:

                T[i][j]=T[i-1][j]

                continue

                

            if left[i][j]==1 and upper[i][j]==1:

                    T[i][j]=0

            elif left[i][j]==0 and upper[i][j]==1:

                    T[i][j]=T[i-1][j]

            elif left[i][j]==1 and upper[i][j]==0:

                    T[i][j]=T[i][j-1]

            else:

                T[i][j]=T[i-1][j]+T[i][j-1]



    if T[gx][gy]==0:

        print("Miserable Hokusai!")

    else:

        print(T[gx][gy])

Submission status: Accepted

Solution code:
N=int(input())
for n in range(N):
    gx,gy=map(int,input().split())
    T=[[0 for i in range(gy+1)] for j in range(gx+1)]
    left=[[0 for i in range(gy+1)] for j in range(gx+1)]
    upper=[[0 for i in range(gy+1)] for j in range(gx+1)]
    p=int(input())
    for i in range(p):       
        x1,y1,x2,y2=map(int,input().split())
        if x1==x2:
            upper[x1][max(y1,y2)]=1
        if y1==y2:
            left[max(x1,x2)][y1]=1

    for i in range(gx+1):
        for j in range(gy+1):
            if i==0:
                left[i][j]=1
            if j==0:
                upper[i][j]=1
    for i in range(gx+1):
        for j in range(gy+1):
            if i==0 and j==0:
                T[i][j]=1
            else:  
                if left[i][j]==1 and upper[i][j]==1:
                    T[i][j]=0
                elif left[i][j]==0 and upper[i][j]==1:
                    T[i][j]=T[i-1][j]
                elif left[i][j]==1 and upper[i][j]==0:
                    T[i][j]=T[i][j-1]
                else:
                    T[i][j]=T[i-1][j]+T[i][j-1]

    if T[gx][gy]==0:
        print("Miserable Hokusai!")
    else:
        print(T[gx][gy])