Problem:


通学経路

問題

太郎君の住んでいるJOI市は，南北方向にまっすぐに伸びる a 本の道路と，東西方向にまっすぐに伸びる b 本の道路により，碁盤の目の形に区分けされている．

南北方向の a 本の道路には，西から順に 1, 2, ... , a の番号が付けられている．また，東西方向の b 本の道路には，南から順に 1, 2, ... , b の番号が付けられている．西から i 番目の南北方向の道路と，南から j 番目の東西方向の道路が交わる交差点を (i, j) で表す．

太郎君は，交差点 (1, 1) の近くに住んでおり，交差点 (a, b) の近くのJOI高校に自転車で通っている．自転車は道路に沿ってのみ移動することができる．太郎君は，通学時間を短くするため，東または北にのみ向かって移動して通学している．

現在， JOI市では， n 個の交差点 (x1, y1), (x2, y2), ... , (xn, yn) で工事を行っている．太郎君は工事中の交差点を通ることができない．

太郎君が交差点 (1, 1) から交差点 (a, b) まで，工事中の交差点を避けながら，東または北にのみ向かって移動して通学する方法は何通りあるだろうか．太郎君の通学経路の個数 m を求めるプログラムを作成せよ．

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．入力はゼロを２つ含む行で終了する．

1行目には，空白を区切りとして2個の整数 a, b が書かれている．これは，南北方向の道路の本数と，東西方向の道路の本数を表す． a, b は 1 ≤ a, b ≤ 16 をみたす．

2行目には, 工事中の交差点の個数を表す整数 n が書かれている． n は 1 ≤ n ≤ 40 をみたす．

続く n 行 (3行目から n+2 行目) には，工事中の交差点の位置が書かれている． i+2 行目には空白で区切られた整数 xi, yi が書かれており，交差点 (xi, yi) が工事中であることを表す． xi, yi は 1 ≤ xi, yi ≤ 16 をみたす． 

データセットの数は 5 を超えない．

出力

データセットごとに, 太郎君の通学経路の個数 m を1行に出力する．

入出力例

入力例
 

5 4  

3  

2 2  

2 3  

4 2  

  　

  出力例

5

-->

入力例

5 4
3
2 2
2 3
4 2
5 4
3
2 2
2 3
4 2
0 0

出力例

5
5

下図は a=5, b=4, n=3 で，工事中の交差点が (2,2), (2,3), (4,2) の場合を表している．

この場合，通学経路は m=5 通りある． 5通りの通学経路を全て図示すると，以下の通り．

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
5 4
3
2 2
2 3
4 2
5 4
3
2 2
2 3
4 2
0 0


Sample output:
5
5

Submission status: Wrong Answer

Solution code:
import copy

while True:
    a, b = map(int, input().split())
    if a == 0:
        break
    N = int(input())
    memo = [[0 for i in range(a+1)] for j in range(b+1)]
    flag = [[False for i in range(a+1)] for j in range(b+1)]
    memo[1][1] = 1
    flag[1][1] = True
    x = [0] * N
    y = [0] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())
        flag[y[i]][x[i]] = True
    print(flag)

    for i in range(1, b+1):
        for j in range(1, a+1):
            if not flag[i][j]:
                flag[i][j] = True
                memo[i][j] = memo[i-1][j] + memo[i][j-1]

    print(memo[b][a])

Submission status: Wrong Answer

Solution code:
while True:
    a, b = map(int, input().split())
    if a == 0:
        break
    N = int(input())
    memo = [[0 for i in range(a+1)] for j in range(b+1)]
    flag = [[False for i in range(a+1)] for j in range(b+1)]
    memo[1][1] = 1
    flag[1][1] = True
    x = [0] * N
    y = [0] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())
        flag[y[i]][x[i]] = True
    print(flag)

    for i in range(1, b+1):
        for j in range(1, a+1):
            if not flag[i][j]:
                flag[i][j] = True
                memo[i][j] = memo[i-1][j] + memo[i][j-1]

    print(memo[b][a])

Submission status: Wrong Answer

Solution code:
while(1):
    [a,b]=[int(x) for x in raw_input().split()]
    if a==0:
        break
    else:
        n=int(raw_input())
        S=[[-1 for x in range(b)] for y in range(a)]
        for i in range(a):
            S[i][0]=1
        for i in range(b):
            S[0][i]=1
        for i in range(n):
            [bx,by]=[int(x) for x in raw_input().split()]
            S[bx-1][by-1]=0
        for h in range(1,b):
            for x in range(1,a):
                if S[x][h]==-1:
                    S[x][h]=S[x-1][h]+S[x][h-1]
        print S[a-1][b-1]

Submission status: Wrong Answer

Solution code:
while True:
    x, y = map(int, raw_input().split())
    if x==0: break
    l = [[True for col in range(x)] for row in range(y)]
    ans = [[1 for col in range(x)] for row in range(y)]
    for i in range(input()):
        dx, dy = map(int, raw_input().split())
        l[dy-1][dx-1] = False
        if dy==1:
            for j in range(dy,y): ans[j][0] = 0
        if dx==1:
            for j in range(dx,x): ans[0][j] = 0
    for i in range(1,y):
        for j in range(1,x):
            if l[i][j]: ans[i][j] = ans[i-1][j] + ans[i][j-1]
            else : ans[i][j] = 0
    print ans[y-1][x-1]

Submission status: Wrong Answer

Solution code:
while 1:
    a,b=map(int,raw_input().split())
    if a==b==0:break
    n=input()
    c=[map(int,raw_input().split()) for _ in xrange(n)]
    dp=[[0]*(b+1) for _ in range(a+1)]
    for i in xrange(a):
        dp[i+1][1]=1
    for i in xrange(b):
        dp[1][i+1]=1
    for i in xrange(1,a):
        for j in xrange(1,b):
            if [i+1,j+1] in c: continue
            dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
    print(dp[a][b])

Submission status: Wrong Answer

Solution code:
com_lis = {}
def com(n,k):
    if k == 1:
        if not (n,k) in com_lis:
            com_lis[(n,k)] = 1
        return 1
    if n == 1:
        if not (n,k) in com_lis:
            com_lis[(n,k)] = 1
        return 1
    
    if not (n - 1,k) in com_lis:
        com_lis[(n -1,k)] = com(n - 1,k)
    if not (n ,k - 1) in com_lis:
        com_lis[(n,k -1)] = com(n,k - 1)
        
    
    com_lis[(n,k)] = com_lis[(n - 1,k)] + com_lis[(n,k - 1)]
    return com_lis[(n,k)]

while True:
   
    n,s = map(int,input().split())
    if [n,s] == [0,0]:
        break
    k = int(input())
    for l in range(k):
        p,q = map(int,input().split())
        com_lis[(p,q)] = 0
        
    print(com(n,s))
    com_lis = {}

Submission status: Wrong Answer

Solution code:
# coding: utf-8

while True:
	a, b = map(int, raw_input().split())
	if a == 0:
		break
	else:
		method = []
		for i in range(a):
			row = []
			if i == 0:
				for j in range(b):
					row.append(1)
			else:
				for j in range(b):
					if j == 0:
						row.append(1)
					else:
						row.append(0)
			method.append(row)
	n = int(raw_input())
	for i in range(n):
		x, y = map(int, raw_input().split())
		method[x-1][y-1] = -1
	for i in range(1,a):
		for j in range(1,b):
			if method[i][j] != -1:
				if method[i-1][j] == -1 and method[i][j-1] == -1:
					method[i][j] = 0
				elif method[i-1][j] == -1 and method[i][j-1] != -1:
					method[i][j] = method[i][j-1]
				elif method[i-1][j] != -1 and method[i][j-1] == -1:
					method[i][j] = method[i-1][j]
				else:
					method[i][j] = method[i-1][j] + method[i][j-1]
	print(method[a-1][b-1])

Submission status: Wrong Answer

Solution code:
while True:
  a,b = map(int,input().split())
  if a == 0 and b == 0:
    break
  n = int(input())
  dp = [[0 for i in range(b)] for j in range(a)]
  for i in range(a):
    dp[i][0] = 1
  for i in range(b):
    dp[0][i] = 1
  for i in range(n):
    i,j = map(int,input().split())
    dp[i - 1][j - 1] = -1
  for i in range(1,a):
    for j in range(1,b):
      if dp[i][j] >= 0:
        dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1],dp[i - 1][j],dp[i][j - 1])
  print(dp[a - 1][b - 1])

Submission status: Wrong Answer

Solution code:
while True:
  a,b = map(int,input().split())
  if a == 0 and b == 0:
    break
  n = int(input())
  dp = [[0 for i in range(b)] for j in range(a)]
  for i in range(a):
    dp[i][0] = 1
  for i in range(b):
    dp[0][i] = 1
  for i in range(n):
    i,j = map(int,input().split())
    dp[i - 1][j - 1] = -1
  for i in range(1,a):
    for j in range(1,b):
      if dp[i][j] >= 0:
        dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1],dp[i - 1][j],dp[i][j - 1])
  if (dp[a - 1][b - 1] <= 0):
    print(0)
  else: print(dp[a - 1][b - 1])

Submission status: Wrong Answer

Solution code:
for e in iter(input,'0 0'):
    a,b=map(int,e.split())
    m=[[0]*-~b for _ in[0]*-~a]
    m[1][1]=1
    for _ in[0]*int(input()):
        i,j=map(int,input().split())
        m[i][j]=-1
    for s in range(a):
        for t in range(b):
            u,v=m[s-1][t],m[s][t-1]
            m[s][t]+=u*(u>0)+v*(v>0)
    print(m[a][b])

Submission status: Wrong Answer

Solution code:
for e in iter(input,'0 0'):
    a,b=map(int,e.split())
    m=[[1]*-~b for _ in[0]*-~a]
    for _ in[0]*int(input()):
        i,j=map(int,input().split())
        m[i][j]=-1
    for s in range(2,a+1):
        for t in range(2,b+1):
            if m[s][t]>0:
                u,v=m[s-1][t],m[s][t-1]
                m[s][t]=u*(u>0)+v*(v>0)
    print(m[a][b])

Submission status: Wrong Answer

Solution code:
# AOJ 0515: School Road
# Python3 2018.6.30 bal4u

while True:
	a, b = map(int, input().split())
	if a == 0: break
	arr = [[0 for b in range(17)] for a in range(17)]
	p = [[0 for b in range(17)] for a in range(17)]
	for i in range(int(input())):
		x, y = map(int, input().split())
		arr[x][y] = 1
	for x in range(1, a+1):
		if arr[x][1] == 0: p[x][1] = 1
	for y in range(1, b+1):
		if arr[1][y] == 0: p[1][y] = 1
	for y in range(2, b+1):
		for x in range(2, a+1):
			if arr[x][y]: continue
			if arr[x-1][y] == 0: p[x][y] += p[x-1][y]
			if arr[x][y-1] == 0: p[x][y] += p[x][y-1]
	print(p[a][b])

Submission status: Wrong Answer

Solution code:
while True:
    a,b=map(int,raw_input().split())
    if a==b==0:break
    n=input()
    stop=[map(int,raw_input().split()) for i in range(n)]
    stop=[[i-1,j-1] for i,j in stop]
    print stop
    dp=[[0]*a for i in range(b)]
    for i in range(a):
        if [i,0] not in stop:
            dp[0][i]=1
    for i in range(b):
        if [0,i] not in stop:
            dp[i][0]=1
    for i in range(1,b):
        for j in range(1,a):
            if [j,i] not in stop:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
    print dp[b-1][a-1]

Submission status: Wrong Answer

Solution code:
while True:
    a,b=map(int,raw_input().split())
    if a==b==0:break
    n=input()
    stop=[map(int,raw_input().split()) for i in range(n)]
    stop=[[i-1,j-1] for i,j in stop]
    dp=[[0]*a for i in range(b)]
    for i in range(a):
        if [i,0] not in stop:
            dp[0][i]=1
    for i in range(b):
        if [0,i] not in stop:
            dp[i][0]=1
    for i in range(1,b):
        for j in range(1,a):
            if [j,i] not in stop:
                dp[i][j]=dp[i-1][j]+dp[i][j-1]
    print dp[b-1][a-1]

Submission status: Wrong Answer

Solution code:
while True:

    n = list(map(int, input().split()))
    if not n[0] and not n[1]:
        break

    data = [[1 if a == 0 or b == 0 else 0 for a in range(n[0])] for b in range(n[1])]

    # m = int(input())
    for i in range(int(input())):
        c = list(map(lambda x: int(x)-1, input().split()))
        data[c[1]][c[0]] = -1

    for j in range(1, n[0]):
        for i in range(1, n[1]):
            if data[i][j] < 0:
                continue

            elif data[i-1][j] < 0:
                data[i][j] = data[i][j-1]

            elif data[i][j-1] < 0:
                data[i][j] = data[i-1][j]

            else:
                data[i][j] = data[i-1][j] + data[i][j-1]


    print(data[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
def solve(x,y):
	if x == a and y == b: return 1
	if x > a or y > b or [x,y] in block: return 0
	return solve(x+1,y) + solve(x,y+1)
	
while 1:
	a,b = map(int,raw_input().split())
	if a == 0: break
	block = [map(int,raw_input().split()) for i in range(input())]
	print solve(1,1)

Submission status: Accepted

Solution code:
while True:
    a, b = map(int, input().split())
    if a == 0:
        break
    N = int(input())
    memo = [[0 for i in range(a+1)] for j in range(b+1)]
    flag = [[False for i in range(a+1)] for j in range(b+1)]
    memo[1][1] = 1
    flag[1][1] = True
    x = [0] * N
    y = [0] * N
    for i in range(N):
        x[i], y[i] = map(int, input().split())
        flag[y[i]][x[i]] = True

    for i in range(1, b+1):
        for j in range(1, a+1):
            if not flag[i][j]:
                flag[i][j] = True
                memo[i][j] = memo[i-1][j] + memo[i][j-1]

    print(memo[b][a])

Submission status: Accepted

Solution code:
#coding:utf-8
 
import sys
import copy
 
def main():
    line = sys.stdin.readline()
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return
 
def analy(line):
    field = [int(n) for n in line.split()]
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        data.append(b)
    print (compute(field, data))
 
def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
                if i == 0 :
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding:utf-8

import sys
import copy

def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return

def analy(line):
    #整列
    field = [int(n) for n in line.split()]
    # 横、縦
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #横、縦
        data.append(b)
    print (compute(field, data))

def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #横→縦に移動していく
                if i == 0 :
                    #一番下
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #左がない
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding:utf-8

import sys
import copy

def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return

def analy(line):
    #??´???
    field = [int(n) for n in line.split()]
    # ?¨???????
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #?¨???????
        data.append(b)
    print (compute(field, data))

def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #?¨???????????§????????????????
                if i == 0 :
                    #?????????
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #????????????
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding:utf-8

import sys
import copy

def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return

def analy(line):
    #????
    field = [int(n) for n in line.split()]
    # ???A?c
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #???A?c
        data.append(b)
    print (compute(field, data))

def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #???¨?c???????????¢??
                if i == 0 :
                    #??????
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #?¶?????¢
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding:utf-8

import sys
import copy

def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return

def analy(line):
    #?°??
    field = [int(n) for n in line.split()]
    # ?£?¢??
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #?£?¢??
        data.append(b)
    print (compute(field, data))

def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #?£¢?????°??°????????
                if i == 0 :
                    #°?????
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #???¬????
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
 
import sys
import copy
 
def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return
 
def analy(line):
    #整列
    field = [int(n) for n in line.split()]
    # 横、縦
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #横、縦
        data.append(b)
    print (compute(field, data))
 
def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #横→縦に移動していく
                if i == 0 :
                    #一番下
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #左がない
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
  
import sys
import copy
  
def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return
  
def analy(line):
    #????
    field = [int(n) for n in line.split()]
    # ???A?c
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #???A?c
        data.append(b)
    print (compute(field, data))
  
def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #???¨?c???????????¢??
                if i == 0 :
                    #??????
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #?¶?????¢
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]
  
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
while(1):
    [a,b]=[int(x) for x in raw_input().split()]
    if a==0:
        break
    else:
        n=int(raw_input())
        S=[[-1 for x in range(b+1)] for y in range(a+1)]
        for i in range(a+1):
            S[i][0]=0
        for i in range(b+1):
            S[0][i]=0
        for i in range(n):
            [bx,by]=[int(x) for x in raw_input().split()]
            S[bx][by]=0
        S[1][1]=1
        for h in range(1,b+1):
            for x in range(1,a+1):
                if S[x][h]==-1:
                    S[x][h]=S[x-1][h]+S[x][h-1]
        print S[a][b]

Submission status: Accepted

Solution code:
while True:
    x, y = map(int, raw_input().split())
    if x==0: break
    l = [[True for col in range(x)] for row in range(y)]
    ans = [[1 for col in range(x)] for row in range(y)]
    for i in range(input()):
        dx, dy = map(int, raw_input().split())
        l[dy-1][dx-1] = False
        if dy==1:
            for j in range(dx-1,x): ans[0][j] = 0
        if dx==1:
            for j in range(dy-1,y): ans[j][0] = 0
    for i in range(1,y):
        for j in range(1,x):
            if l[i][j]: ans[i][j] = ans[i-1][j] + ans[i][j-1]
            else : ans[i][j] = 0 
    print ans[y-1][x-1]

Submission status: Accepted

Solution code:
while True:
    w, h = map(int, input().split())
    if not w and not h:
        break

    n = int(input())
    constructions = set(tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(n))

    patterns = [[0] * w for _ in range(h)]
    patterns[0][0] = 1
    for j in range(1, w):
        if (j, 0) in constructions:
            break
        patterns[0][j] = 1
    for i in range(1, h):
        if (0, i) in constructions:
            break
        patterns[i][0] = 1
    for i in range(1, h):
        for j in range(1, w):
            if (j, i) in constructions:
                continue
            patterns[i][j] = patterns[i - 1][j] + patterns[i][j - 1]
    print(patterns[-1][-1])

Submission status: Accepted

Solution code:
while 1:
    a,b=map(int,raw_input().split())
    if a==b==0:break
    n=input()
    c=[map(int,raw_input().split()) for _ in xrange(n)]
    dp=[[0]*(b+1) for _ in xrange(a+1)]
    for i in xrange(a):
        if [i+1,1] in c: break
        dp[i+1][1]=1
    for i in xrange(b):
        if [1,i+1] in c: break
        dp[1][i+1]=1
    for i in xrange(1,a):
        for j in xrange(1,b):
            if [i+1,j+1] in c: continue
            dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1]
    print(dp[a][b])

Submission status: Accepted

Solution code:
from functools import lru_cache


def main():
    while True:
        W, H = map(int, input().split(" "))
        if H == W == 0:
            break

        N = int(input())
        forbid = {tuple(map(int, input().split(" "))) for _ in range(N)}

        @lru_cache(maxsize=None)
        def route(x, y):
            if x == 0 or y == 0:
                return 0 
            if (x, y) in forbid:
                return 0
            if x == y == 1:
                return 1
            return route(x - 1, y) + route(x, y - 1)

        print(route(W, H))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    while True:
        a, b = map(int, input().split())
        if a == b == 0:
            break

        n = int(input())
        construction = [list(map(int, input().split())) for _ in range(n)]

        dp = [[0]*b]*a

        dp[0][0] = 1

        for i in range(a):
            for j in range(b):
                if i == 0 and j == 0:
                    continue
                
                if any(list([i+1, j+1] == construction[k] for k in range(n))):
                    dp[i][j] = 0
                    continue

                w1 = 0
                w2 = 0
                
                if i > 0:
                    w1 = dp[i-1][j]

                if j > 0:
                    w2 = dp[i][j-1];
                dp[i][j] = w1 + w2

        print(dp[a-1][b-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy

xy = [[0 for i in range(20)] for i in range(20)]
no = deepcopy(xy)

def rec(n, m):
    if no[n][m]:
        return 0
    if n == 0 or m == 0:
        return 0
    if n == 1 and m == 1:
        return 1

    xy[n][m] = rec(n - 1, m) + rec(n, m - 1)
    return xy[n][m]

def main():
    global xy, no
    while True:
        a, b = map(int, input().split())
        if a == b == 0:
            break

        n = int(input())
        for i in range(n):
            x, y = map(int, input().split())
            no[x][y] = 1

        print(rec(a, b))
        
        xy = deepcopy([[0 for i in range(20)] for i in range(20)])
        no = deepcopy(xy)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
com_lis = {}
def com(n,k):
    if k == 1:
        if not (n,k) in com_lis:
            com_lis[(n,k)] = 1
        return 1
    if n == 1:
        if not (n,k) in com_lis:
            com_lis[(n,k)] = 1
        return 1
    
    if not (n - 1,k) in com_lis:
        com_lis[(n -1,k)] = com(n - 1,k)
    if not (n ,k - 1) in com_lis:
        com_lis[(n,k -1)] = com(n,k - 1)
        
    
    com_lis[(n,k)] = com_lis[(n - 1,k)] + com_lis[(n,k - 1)]
    return com_lis[(n,k)]

while True:
   
    n,s = map(int,input().split())
    if [n,s] == [0,0]:
        break
    k = int(input())
    for l in range(k):
        p,q = map(int,input().split())
        if p == 1:
            for i in range(q,s+1):
                com_lis[(1,i)] = 0
        if q == 1:
            for j in range(p,n + 1):
                com_lis[(j,1)] = 0
        com_lis[(p,q)] = 0
        
    print(com(n,s))
    com_lis = {}

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0515

"""
import sys
from sys import stdin
input = stdin.readline


def solve(a, b):
    n = int(input())
    impassables = [tuple(map(int, input().split())) for _ in range(n)]
    dp = [[0] * (a+1) for _ in range(b+1)]
    dp[0][1] = 1

    for y in range(1, b+1):
        for x in range(1, a+1):
            if (x, y) not in impassables:
                dp[y][x] = dp[y-1][x] + dp[y][x-1]
    return dp[-1][-1]


def main(args):
    while True:
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            break
        result = solve(a, b)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# coding: utf-8

while True:
	a, b = map(int, raw_input().split())
	if a == 0:
		break
	else:
		method = []
		for i in range(a):
			row = []
			for j in range(b):
				row.append(0)
			method.append(row)
	n = int(raw_input())
	for i in range(n):
		x, y = map(int, raw_input().split())
		method[x-1][y-1] = -1
	for j in range(b):
		if method[0][j] == -1:
			break
		else:
			method[0][j] = 1
	for i in range(a):
		if method[i][0] == -1:
			break
		else:
			method[i][0] = 1
	for i in range(1,a):
		for j in range(1,b):
			if method[i][j] != -1:
				if method[i-1][j] == -1 and method[i][j-1] == -1:
					method[i][j] = 0
				elif method[i-1][j] == -1 and method[i][j-1] != -1:
					method[i][j] = method[i][j-1]
				elif method[i-1][j] != -1 and method[i][j-1] == -1:
					method[i][j] = method[i-1][j]
				else:
					method[i][j] = method[i-1][j] + method[i][j-1]
	#print(method)
	print(method[a-1][b-1])

Submission status: Accepted

Solution code:
def main():
	while True:
		w,h=map(int,input().split())
		if w==0 and h==0:
			break
		ok=[[True for j in range(w)] for i in range(h)]
		n=int(input())
		for i in range(n):
			x,y=map(int,input().split())
			ok[y-1][x-1]=False
		dp=[[0 for j in range(w)] for i in range(h)]
		dp[0][0]=1
		for i in range(h):
			for j in range(w):
				if i+1<h and ok[i+1][j]:
					dp[i+1][j]+=dp[i][j]
				if j+1<w and ok[i][j+1]:
					dp[i][j+1]+=dp[i][j]
		print(dp[h-1][w-1])

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
while True:
  a,b = map(int,input().split())
  if a == 0 and b == 0:
    break
  n = int(input())
  dp = [[0 for i in range(b)] for j in range(a)]
  for i in range(n):
    i,j = map(int,input().split())
    dp[i - 1][j - 1] = -1

  for i in range(a):
    if dp[i][0] == -1:
      break
    else:
      dp[i][0] = 1
  for i in range(b):
    if dp[0][i] == -1:
      break
    else:
      dp[0][i] = 1
  for i in range(1,a):
    for j in range(1,b):
      if dp[i][j] >= 0:
        dp[i][j] = max(dp[i - 1][j] + dp[i][j - 1],dp[i - 1][j],dp[i][j - 1])
  if (dp[a - 1][b - 1] <= 0):
    print(0)
  else: print(dp[a - 1][b - 1])

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
    a,b=map(int,e.split())
    m=[[0]*-~b for _ in[0]*-~a]
    m[1][1]=1
    for _ in[0]*int(input()):
        i,j=map(int,input().split())
        m[i][j]=-1
    for k in range(3,a+b+1):
        for l in range(1,k):
            if l<=a and k-l<=b and m[l][k-l]>=0:
             s,t=m[l-1][k-l],m[l][k-l-1]
             m[l][k-l]=s*(s>0)+t*(t>0)
    print(m[a][b])

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
    a,b=map(int,e.split())
    m=[[0]*b for _ in[0]*a]
    for _ in[0]*int(input()):
        i,j=map(int,input().split())
        m[~-i][~-j]=-1
    for s in range(a):
        for t in range(b):
            u,v=m[s-1][t],m[s][t-1]
            m[s][t]=(u*(u>0)+v*(v>0))*(m[s][t]!=-1)+(s+t==0)
    print(m[~-a][~-b])

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 a,b=map(int,e.split())
 m=[[0]*b for _ in[0]*a]
 for _ in[0]*int(input()):
  i,j=map(int,input().split())
  m[~-i][~-j]=-1
 for s in range(a):
  for t in range(b):
   u,v=m[s-1][t],m[s][t-1]
   m[s][t]=(u*(u>0)+v*(v>0))*(m[s][t]!=-1)+(s+t==0)
 print(m[~-a][~-b])

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 a,b=map(int,e.split())
 m=[[0]*b for _ in[0]*a]
 for _ in[0]*int(input()):
  i,j=map(int,input().split())
  m[~-i][~-j]=-1
 for s in range(a):
  for t in range(b):
   u,v=m[s-1][t],m[s][t-1]
   if m[s][t]>=0:m[s][t]=(u*(u>0)+v*(v>0))+(s+t==0)
 print(m[~-a][~-b])

Submission status: Accepted

Solution code:
# AOJ 0515: School Road
# Python3 2018.6.30 bal4u

while True:
	a, b = map(int, input().split())
	if a == 0: break
	arr = [[0 for b in range(b+1)] for a in range(a+1)]
	p = [[0 for b in range(b+1)] for a in range(a+1)]
	for i in range(int(input())):
		x, y = map(int, input().split())
		arr[x][y] = 1
	for x in range(1, a+1):
		if arr[x][1]: break
		p[x][1] = 1
	for y in range(1, b+1):
		if arr[1][y]: break
		p[1][y] = 1
	for y in range(2, b+1):
		for x in range(2, a+1):
			if arr[x][y]: continue
			if arr[x-1][y] == 0: p[x][y] += p[x-1][y]
			if arr[x][y-1] == 0: p[x][y] += p[x][y-1]
	print(p[a][b])

Submission status: Accepted

Solution code:
#!/usr/bin/python

def readints(f):
    return map(int, f.readline().split())

def count(a, b, detours):
    xy = {}
    for i in range(0, a+1):
        xy[(i, 0)] = 0
    for j in range(0,  b+1):
        xy[(0, j)] = 0

    for i, j in detours:
        xy[(i, j)] = 0
    xy[(1, 1)] = 1

    for i in range(1, a+1):
        for j in range(1,  b+1):
            m = xy.get((i, j), None)
            if m is None:
                xy[(i,j)] = xy[(i-1, j)] + xy[(i, j-1)]
    return xy[(a,b)]

import sys

f = sys.stdin
a, b = readints(f)
while a and b:
    n, = readints(f)
    detours = set()
    for i in range(n):
        detours.add(tuple(readints(f)))
    print count(a, b, detours)
    a, b = readints(f)