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: 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[0][0]=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(16)] for j in range(16)]
    left=[[0 for i in range(16)] for j in range(16)]
    upper=[[0 for i in range(16)] for j in range(16)]
    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(16):
        for j in range(16):
            if i==0 and j==0:
                T[i][j]=1
            elif i==0 and j>=1 and upper[i][j]==0:
                T[i][j]=T[i][j-1]
            elif i>=1 and j==0 and left[i][j]==0:
                T[i][j]=T[i-1][j]
            else:
                if left[i][j]==1 and upper[i][j]==1:
                    T[i][j]=0
                if left[i][j]==0 and upper[i][j]==1:
                    T[i][j]=T[i-1][j]
                if left[i][j]==1 and upper[i][j]==0:
                    T[i][j]=T[i][j-1]
                if left[i][j]==0 and upper[i][j]==0:
                    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 i in range(n):
    gx,gy=map(int,input().split())
    L1=[[0 for y in range(16)]for x in range(16)]#縦
    L2=[[0 for y in range(16)]for x in range(16)]#横
    L3=[[0 for y in range(16)]for x in range(16)]#格子

    matatabi=int(input())
    for i in range(matatabi):
        x1,y1,x2,y2=map(int,input().split())
        if x1==x2:
            L1[max(y1,y2)][x1]=1
        else:
            L2[y1][max(x1,x2)]=1

    for y in range(gy+1):
        for x in range (gx+1):
            if x==y==0:
                L3[y][x]=1
            elif L1[y][x]==L2[y][x]==1:
                L3[y][x]=0
            elif (L1[y][x]==1 or L2[y][x]==1) and (y==0 or x==0):
                L3[y][x]=0
            elif y==0 or L1[y][x]==1:
                L3[y][x]=L3[y][x-1]
            elif x==0 or L2[y][x]==1:
                L3[y][x]=L3[y-1][x]
            else:
                L3[y][x]=L3[y][x-1]+L3[y-1][x]

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

Submission status: Accepted

Solution code:
d=int(input())
for i in range(d):
    gx,gy=map(int,input().split())
    L1=[[0 for y in range(16)]for x in range(16)]#たて
    L2=[[0 for y in range(16)]for x in range(16)]#よこ
    L3=[[0 for y in range(16)]for x in range(16)]#結果

    m=int(input())
    for i in range(m):
        x1,y1,x2,y2=map(int,input().split())
        if x1==x2:
            L1[max(y1,y2)][x1]=1
        else:
            L2[y1][max(x1,x2)]=1

    for y in range(gy+1):
        for x in range (gx+1):
            if x==y==0:
                L3[y][x]=1
            elif L1[y][x]==L2[y][x]==1:
                L3[y][x]=0
            elif (L1[y][x]==1 or L2[y][x]==1) and (y==0 or x==0):
                L3[y][x]=0
            elif y==0 or L1[y][x]==1:
                L3[y][x]=L3[y][x-1]
            elif x==0 or L2[y][x]==1:
                L3[y][x]=L3[y-1][x]
            else:
                L3[y][x]=L3[y][x-1]+L3[y-1][x]

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

Submission status: Accepted

Solution code:
N=int(input())

for n in range(N):
    gx,gy=map(int,input().split())
    T=[[0 for j in range(gy+1)] for i in  range(gx+1)]
    under=[[0 for j in range(gy+1)] for i in range(gx+1)]
    left=[[0 for j in range(gy+1)] for i in range(gx+1)]
    
    p=int(input())
    
    for i in range(p):
        x1,y1,x2,y2=map(int,input().split())
        if x1==x2:
            under[x1][max(y1,y2)]=1
        if y1==y2:
            left[max(x1,x2)][y1]=1
            
    for j in range(gy+1):
        for i in range(gx+1):
            T[0][0]=1
            if i==0:
                T[i][j]=1
            if j==0:
                T[i][j]=1
            if under[i][j]==0 and left[i][j]==0:
                T[i][j]=T[i-1][j]+T[i][j-1] 
            if under[i][j]==1 and left[i][j]==1:
                T[i][j]=0 
            elif under[i][j]==1:
                T[i][j]=T[i-1][j]
            elif left[i][j]==1:
                T[i][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
            elif upper[i][j]==1 and left[i][j]==1:
                T[i][j]=0
            elif (upper[i][j]==1 or left[i][j]==1) and (i==0 or j==0):
                T[i][j]=0
            elif i==0:
                T[i][j]=T[i][j-1]
            elif j==0:
                T[i][j]=T[i-1][j] 
            elif upper[i][j]==1:
                T[i][j]=T[i-1][j]
            elif left[i][j]==1:
                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 l in range(n):
    gx,gy=map(int,input().split())
    Count= [[0 for j in range(16)] for i in range(16)] 
    Grid= [[0 for j in range(16)] for i in range(16)] 
    
    for i in range(int(input())):
        x1,y1,x2,y2=map(int,input().split())
        if x1==x2:
            Grid[x1][max(y1,y2)]=Grid[x1][max(y1,y2)]+1
        else:
            Grid[max(x1,x2)][y1]=Grid[max(x1,x2)][y1]+2
            
                    
    for i in range (16):
        if(Grid[0][i]!=0):
            break
        Count[0][i]=1
    for i in range (16):
        if(Grid[i][0]!=0):
            break
        Count[i][0]=1
        
    for i in range(1,16):
        for j in range(1,16):
            k=Grid[i][j]
            if k==0:
                Count[i][j]=Count[i-1][j]+Count[i][j-1]
            elif k==1:
                Count[i][j]=Count[i-1][j]
            elif k==2:
                Count[i][j]=Count[i][j-1]
    

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

Submission status: Accepted

Solution code:
x=int(input())
for i in range(x):
    gx,gy=map(int,input().split())
    HK= [[0 for j in range(16)] for i in range(16)]
    mttb=[[0 for j in range(16)] for i in range(16)]
    
    for i in range(int(input())):
        x1,y1,x2,y2=map(int,input().split())
        if x1==x2:
            mttb[x1][max(y1,y2)]+=1
        else:
            mttb[max(x1,x2)][y1]+=2
            
    for i in range(16):
        if(mttb[0][i]!=0):
            break
        HK[0][i]=1
    for i in range(16):
        if(mttb[i][0]!=0):
            break
        HK[i][0]=1
        
    for i in range(1,16):
        for j in range(1,16):
            k=mttb[i][j]
            if k==0:
                HK[i][j]=HK[i-1][j]+HK[i][j-1]
            elif k==1:
                HK[i][j]=HK[i-1][j]
            elif k==2:
                HK[i][j]=HK[i][j-1]
                
    ans=HK[gx][gy]
    if ans==0:
        print("Miserable Hokusai!")
    else:
        print(ans)

Submission status: Accepted

Solution code:
n=int(input())
for i in range(n):
    x,y=map(int,input().split())
    lista=[[0 for i in range(y+1)] for j in range(x+1)]
    m=int(input())
    listb=[]
    if m!=0:
        for j in range(m):
            listc=list(map(int,input().split()))
            listb.append(listc)
    for i in range(1,x+1):
        if [i,0,i-1,0] in listb or [i-1,0,i,0] in listb:
          break
        lista[i][0]=1
    for i in range(1,y+1):
        if [0,i,0,i-1] in listb or [0,i-1,0,i] in listb:
          break
        lista[0][i]=1
    for i in range(1,y+1):
        for j in range(1,x+1):
            if ([j,i,j,i-1] in listb or [j,i-1,j,i] in listb) and ([j,i,j-1,i] in listb or [j-1,i,j,i] in listb):
                lista[j][i]=0
            elif ([j-1,i,j,i] in listb or [j,i,j-1,i] in listb):
                lista[j][i]=lista[j][i-1]
            elif ([j,i-1,j,i] in listb or [j,i,j,i-1] in listb):
                lista[j][i]=lista[j-1][i]
            else:
                lista[j][i]=lista[j-1][i]+lista[j][i-1]
    if lista[x][y]==0:
      print("Miserable Hokusai!")
    else:
      print(lista[x][y])

Submission status: Accepted

Solution code:
for _ in range(int(input())):
    X, Y = map(int,input().split())
    m = int(input())
    Judge = [[[0] * 2 for i in range(Y+1)] for j in range(X+1)]
    # Judはある点(x, y)において左から通路があるか、また上から通路あるかを判定するための配列
    # 形式は
    # [x座標][y座標][0] = 0：点(x, y)において左からの通路あり
    # [x座標][y座標][0] = 1：点(x, y)において左からの通路なし
    # [x座標][y座標][1] = 0：点(x, y)において上からの通路あり
    # [x座標][y座標][1] = 1：点(x, y)において上からの通路なし
    for i in range(Y+1):
        Judge[0][i][0] = 1
    for j in range(X+1):
        Judge[j][0][1] = 1
    # 端っこの点は上から、または左からの通路が絶対にない
    Tot = [[0] * (Y+1) for i in range(X+1)] #Tot[x座標][y座標]が、点(x, y)まで行ける道の数
    Tot[0][0] = 1

    for i in range(m):
        A = list(map(int, input().split()))
        x1 = A[0]
        y1 = A[1]
        x2 = A[2]
        y2 = A[3]
        if x1 == x2:
            if y2 > y1:
                Judge[x2][y2][1] = 1
                # (x,y)→(x,y+1)にマタタビがあるということだからJudge[x][y+1][0]＝1
            else:
                Judge[x2][y1][1] = 1
        if y1 == y2:
            if x2 > x1:
                Judge[x2][y2][0] = 1
            else:
                Judge[x1][y2][0] = 1
                
    # print(Judge)→デバックで使いました。
        
    for i in range(X+1):
        for j in range(Y+1):
            if Judge[i][j][0] == 0:
                Tot[i][j] += Tot[i-1][j]
            if Judge[i][j][1] == 0:
                Tot[i][j] += Tot[i][j-1]

    if Tot[X][Y] == 0:
        print("Miserable Hokusai!")
    else:
        print(Tot[X][Y])

Submission status: Accepted

Solution code:
nn= int(input())
for _ in range(0,nn):
    gx,gy = map(int,input().split())
    p=int(input())
    m_vert,m_horiz=[],[]
    for _ in range(0,p):
        a,b,c,d = map(int, input().split())
        if a==c:
            if b < d:  # b > d nisuru
                b,d = d,b
            m_vert.append([a,b])
        elif b==d:
            if a < c:
                a,c= c,a
            m_horiz.append([a,b])

    ans= [[0]*(gx+100) for _ in range(gy+100)]
    horiz= [[True]*(gx+100) for _ in range(gy+100)]
    vert= [[True]*(gx+100) for _ in range(gy+100)]
    for i in m_horiz:
        horiz[i[0]][i[1]] = False
    for i in m_vert:
        vert[i[0]][i[1]] = False

    for i in range(0,gx+1):
        for j in range(0,gy+1):
            if i==0 and j==0:
                ans[0][0]=1
            if i!=0 and horiz[i][j] :
                ans[i][j] += ans[i-1][j]
            if j!=0 and vert[i][j] :
                ans[i][j] += ans[i][j-1]

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

Submission status: Accepted

Solution code:
#平安京
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2186&lang=jp
#AOJでは、numpyは、使えなかった。
#当初、行と列の設定を間違えて大変なことになった。どっちがx、どっちがyが普通なんですかね。縦をyにすると添字はyxの順番になってしまう。
#バーチャルマタタビを置いたのが勉強になった。もっとも、行列を結合しようとして、「なぜか」うまくいかなかった。

#import numpy as np
n = int(input())
for i in range (n):
  gx,gy = map(int,input().split())
  m = int(input())
  #Vert = np.concatenate([np.full((gx+1,1),False),np.full((gx+1,gy),True)])
  #Horiz = np.concatenate([np.full((1,gy+1),False),np.full((gx,gy+1),True)],1)
  Vert = [[True]*(gx+1) for i in range(gy+1)]
  #print(Vert)
  Horiz = [[True]*(gx+1) for i in range(gy+1)]
  #print(Horiz)
  for k in range(gx+1):
    #Vert[k][0] = False
    Vert[0][k] = False
    #print(Vert)
  for l in range(gy+1):
    #Horiz[0][l] = False
    Horiz[l][0] = False
    #print(Horiz)
  for j in range(m):
    x1,y1,x2,y2 = map(int,input().split())
    if x1 == x2:
      Vert[max(y1,y2)][x1] = False
    else:
      Horiz[y1][max(x1,x2)] = False
  dp = [[0]*(gx+1) for i in range(gy+2)]
  dp[0][0] = 1
  for k in range(gx+1):
    for l in range(gy+1):
      if Vert[l][k]:
        dp[l][k] += dp[l-1][k]
      if Horiz[l][k]:
        dp[l][k] += dp[l][k-1]
  if dp[gy][gx] == 0:
    print("Miserable Hokusai!")
  else:
    print(dp[gy][gx])

Submission status: Accepted

Solution code:
def solve():
    gx, gy = map(int,input().split())
    N = int(input())
    X = set()#x軸平行な道にマタタビがあるときのゴールに近い方の座標
    Y = set()#y軸平行な道にマタタビがあるときのゴールに近い方の座標
    for i in range(N):
        x1, y1, x2, y2 = map(int,input().split())
        if x1 == x2:
            Y |= {(x2, max(y1, y2))}
        else:
            X |= {(max(x1, x2), y2)}
    ans = [[0 for i in range(gx + 1)] for j in range(gy + 1)]
    ans[0][0] = 1
    for y in range(gy + 1):
        for x in range(gx + 1):
            if y == 0:
                if (x, y) in X or x == 0:
                    pass
                else:
                    ans[y][x] = ans[y][x-1]
            else:
                if x == 0:
                    if (x, y) in Y:
                        pass
                    else:
                        ans[y][x] = ans[y-1][x]
                else:
                    if (x, y) in X and (x, y) in Y:
                        ans[y][x] = 0
                    elif (x, y) in X:
                        ans[y][x] = ans[y-1][x]
                    elif (x, y) in Y:
                        ans[y][x] = ans[y][x-1]
                    else:
                        ans[y][x] = ans[y-1][x] + ans[y][x-1]
    return ans[gy][gx]
p = int(input())
for _ in range(p):
    a = solve()
    if a == 0:
        print('Miserable Hokusai!')
    else:
        print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def solve():
    W,H = map(int,input().split())
    M = int(input())
    impossible = {tuple(map(int,input().split())) for _ in range(M)}
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][0] = 1
    for i in range(H + 1):
        for j in range(W + 1):
            if i + 1 <= H:
                if (j,i,j,i + 1) not in impossible and (j,i + 1,j,i) not in impossible:
                    dp[i + 1][j] += dp[i][j]
            if j + 1 <= W:
                if (j,i,j + 1,i) not in impossible and (j + 1,i,j,i) not in impossible:
                    dp[i][j + 1] += dp[i][j]
    print(dp[-1][-1] if dp[-1][-1] > 0 else "Miserable Hokusai!")

def main():
    N = int(input())
    for _ in range(N):
        solve()
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ライブラリのインポート
#import re #正規表現
#import sys
#import heapq
#import collections
#import math

def main():
    n = int(input())
    for x in range(n):
        gx ,gy = map(int,input().split())
        p = int(input())
        Y = [[0 for i in range(gy+1)] for j in range(gx+1)]
        for i in range(gx+1):
            Y[i][0] += 1
        for i in range(gy+1):
            Y[0][i] += 2
        for i in range(p):
            a, b, c, d = map(int,input().split())
            if a == c:
                if b > d: Y[a][b] += 1
                else: Y[c][d] += 1
            else:
                if a > c: Y[a][b] += 2
                else: Y[c][d] += 2
        Z = [[0 for i in range(gy+1)] for j in range(gx+1)]
        for i in range(gx+1):
            for j in range(gy+1):
                s = Y[i][j]
                if (i,j) == (0,0):  Z[0][0] = 1
                elif s == 3: Z[i][j] = 0
                elif s == 2: Z[i][j] = Z[i][j-1]
                elif s == 1: Z[i][j] = Z[i-1][j]
                else: Z[i][j] = Z[i-1][j] + Z[i][j-1]
        print(Z[gx][gy]) if Z[gx][gy]>0 else print("Miserable Hokusai!")








    
    


    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
def heian():
    x,y = map(int, input().split())
    mata = int(input())
    Vert = [['T' for i in range(x+1)] for j in range(y+1)]
    Horiz = [['T' for i in range(x+1)] for j in range(y+1)]
    for i in range (x+1):
        Vert[0][i] = 'F'
    for i in range (y+1):
        Horiz[i][0] = 'F'
    for i in range(mata):
        a, b, c, d = map(int, input().split())
        if a==c and b<d:
            Vert[d][c] = 'F'
        elif a==c and b>d:
            Vert[b][a] = 'F'
        elif b==d and a>c:
            Horiz[b][a] = 'F'
        else:
            Horiz[d][c] = 'F'
    route =  [[0 for i in range(x+1)] for i in range(y+1)]
    route[0][0] = 1
    for i in range (x+1):
        for j in range(y+1):
            if Vert[j][i] == 'T':
                route[j][i] += route[j-1][i]
            if Horiz[j][i] == 'T':
                route[j][i] += route[j][i-1]
    if route[y][x] > 0:
            return route[y][x]
    else:
        return 'Miserable Hokusai!'
for i in range(n):
    print(heian())

Submission status: Accepted

Solution code:
z=int(input())
for _ in range(z):
    gx,gy = map(int,input().split())
    p=int(input())
    mat=[tuple(map(int,input().split())) for _ in range(p)]
    dp=[[0]*(gy+1) for _ in range(gx+1)]
     
    x0=gx
    y0=gy
    for x1,y1,x2,y2 in mat:
        if x1+x2==0: y0=min(y0,min(y1,y2))
        if y1+y2==0: x0=min(x0,min(x1,x2))
    for i in range(x0+1):
        dp[i][0]=1
    for i in range(y0+1):
        dp[0][i]=1
     
    for y in range(1,gy+1):
        for x in range(1,gx+1):
            a=0
            if (x-1,y,x,y) not in mat and (x,y,x-1,y) not in mat:
                a+=dp[x-1][y]
            if (x,y-1,x,y) not in mat and (x,y,x,y-1) not in mat:
                a+=dp[x][y-1]
            dp[x][y]=a
    print(dp[-1][-1] or "Miserable Hokusai!")

Submission status: Accepted

Solution code:
z=int(input())
for _ in range(z):
    gx,gy = map(int,input().split())
    p=int(input())
    mat=[tuple(map(int,input().split())) for _ in range(p)]
    dp=[[0]*(gy+1) for _ in range(gx+1)]
    
    x0=gx
    y0=gy
    for x1,y1,x2,y2 in mat:
        if x1+x2==0: y0=min(y0,min(y1,y2))
        if y1+y2==0: x0=min(x0,min(x1,x2))
    for i in range(x0+1):
        dp[i][0]=1
    for i in range(y0+1):
        dp[0][i]=1
    
    for y in range(1,gy+1):
        for x in range(1,gx+1):
            a=0
            if (x-1,y,x,y) not in mat and (x,y,x-1,y) not in mat:
                a+=dp[x-1][y]
            if (x,y-1,x,y) not in mat and (x,y,x,y-1) not in mat:
                a+=dp[x][y-1]
            dp[x][y]=a
    print(dp[-1][-1] or "Miserable Hokusai!")

Submission status: Accepted

Solution code:
n=int(input())
for i in range(n):
    x,y=map(int,input().split())
    l=[[0 for i in range(y+1)] for j in range(x+1)]
    m=int(input())
    l1=[]#マタタビの落ちている区間のリスト
    if m!=0:
        for j in range(m):
            l2=list(map(int,input().split()))
            l1.append(l2)
    for i in range(1,x+1):
        if [i,0,i-1,0] in l1 or [i-1,0,i,0] in l1:
          break
        l[i][0]=1
    for i in range(1,y+1):
        if [0,i,0,i-1] in l1 or [0,i-1,0,i] in l1:
          break
        l[0][i]=1
    for i in range(1,y+1):
        for j in range(1,x+1):#2重ループで各点の到達方法の場合の数を記録
            if ([j,i-1,j,i] in l1 or [j,i,j,i-1] in l1) and ([j,i,j-1,i] in l1 or [j-1,i,j,i] in l1):
                l[j][i]=0
            elif ([j,i,j-1,i] in l1 or [j-1,i,j,i] in l1):
                l[j][i]=l[j][i-1]
            elif ([j,i-1,j,i] in l1 or [j,i,j,i-1] in l1):#マタタビの落ちている区間は除く
                l[j][i]=l[j-1][i]
            else:
                l[j][i]=l[j-1][i]+l[j][i-1]
    if l[x][y]==0:
      print("Miserable Hokusai!")
    else:
      print(l[x][y])

Submission status: Accepted

Solution code:
def dp(Map,i,j):
    ans = 0
    if i == 0 and j == 0:
        return 1
    elif Map[i][j] >= 0:
        return Map[i][j]
    else:
        if i>0:
            if vert[i-1][j]:
                ans += dp(Map,i-1,j)
        if j>0:
            if hori[i][j-1]:
                ans += dp(Map,i,j-1)
        Map[i][j] = ans
        return dp(Map,i,j)
n = int(input())
for _ in range(n):
    gx,gy = map(int,input().split())
    m = int(input())
    matatabi = []
    for _ in range(m):
        matatabi.append(list(map(int,input().split())))
    hori = [[True]*(gx+1) for _ in range(gy+1)]
    vert = [[True]*(gx+1) for _ in range(gy+1)]
    for lis in matatabi:
        if lis[0] == lis[2]:
            vert[min(lis[1],lis[3])][lis[0]] = False
        if lis[1] == lis[3]:
            hori[lis[1]][min(lis[0],lis[2])] = False
    Map = [[-1]*(gx+1) for _ in range(gy+1)]
    ans = dp(Map,gy,gx)
    if ans > 0:
        print(ans)
    elif ans == 0:
        print("Miserable Hokusai!")

Submission status: Accepted

Solution code:
def f(x,y,out,dp):
    if dp[y][x] != "#":
        return dp[y][x]
    if [[x-1,y],[x,y]] in out:
        if [[x,y-1],[x,y]] in out:
            dp[y][x] = 0
            return 0
        else:
            dp[y][x] = f(x,y-1,out,dp)
            return dp[y][x]
    if [[x,y-1],[x,y]] in out:
        dp[y][x] = f(x-1,y,out,dp)
        return dp[y][x]
    else:
        dp[y][x] = f(x-1,y,out,dp)+f(x,y-1,out,dp)
        return dp[y][x]

def solve():
    gx,gy = map(int,input().split())
    p = int(input())
    out = []
    for i in range(p):
        x1,y1,x2,y2 = map(int,input().split())
        out.append([[min(x1,x2)+1,min(y1,y2)+1],[max(x1,x2)+1,max(y1,y2)+1]])
    
    dp = [[0]*(gx+2)]
    for i in range(gy+1):
        dp.append([0]+["#"]*(gx+1))
    dp[1][1] = 1
    ans = f(gx+1,gy+1,out,dp)
    if ans == 0:
        print("Miserable Hokusai!")
    else:
        print(ans)
        #for i in dp:
        #    print(i)
    return 0

n = int(input())
for i in range(n):
    solve()

Submission status: Runtime Error

Solution code:
trial = int(input())

for t in range(trial):
    targ = [int(n) for n in f.readline().split(' ')]
    root = [[0 for n in range(targ[0] + 1)] for m in range(targ[1] + 1)]
    matanum = int(f.readline())
    for m in range(matanum):
        matax,matay,secx,secy = (int(n) for n in f.readline().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]])