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: Accepted

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
        else:
            break
    for i in range(b):
        if [0,i] not in stop:
            dp[i][0]=1
        else:
            break
    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: Accepted

Solution code:
import sys

#fp = open("input.txt", "r")
fp = sys.stdin

def isUnderConstruction(address, construction):
    for li in construction:
        if address[0] == li[0] and address[1] == li[1]:
            return True
    return False

while True:
    size = map(int, fp.readline()[:-1].split(" "))
    if size[0] + size[1] == 0:
        break

    n = int(fp.readline()[:-1])

    construction = []
    for i in xrange(n):
        element = map(int, fp.readline()[:-1].split(" "))
        construction.append(element)

    urban = []
    for i in range(size[1]+1):
        element = []
        for j in range(size[0]+1):
            if i == 0 or j == 0:
                element.append(0)
                continue
            if i == 1 and j == 1:
                element.append(1)
                continue
            if isUnderConstruction([j, i], construction):
                element.append(0)
            else:
                element.append(urban[i-1][j] + element[j-1])
        urban.append(element)
    print urban[size[1]][size[0]]

Submission status: Accepted

Solution code:
p = [[0 for i in xrange(17)] for j in xrange(17)]
while 1:
    a,b = map(int, raw_input().split())
    if a==b==0: break
    n = input()
    for i in xrange(b):
        for j in xrange(a):
            p[i][j] = 0
    for i in xrange(n):
        x,y = map(int, raw_input().split())
        p[y-1][x-1] = -10**6
    p[0][0] = 1
    for i in xrange(b):
        for j in xrange(a):
            if p[i][j]<0: continue
            p[i+1][j] += p[i][j]; p[i][j+1] += p[i][j];
    print p[b-1][a-1]

Submission status: Accepted

Solution code:
while True:
    a, b = map(int, raw_input().split())
    if a | b == 0:
        break
    v = [map(int, raw_input().split()) for _ in xrange(input())]
    dp = [[0] * (a + 2) for _ in xrange(b + 2)]
    dp[1][1] = 1
    for y in xrange(1, b + 1):
        for x in xrange(1, a + 1):
            if not [x, y] in v:
                dp[y + 1][x] += dp[y][x]
                dp[y][x + 1] += dp[y][x]
    print dp[b][a]

Submission status: Accepted

Solution code:
while 1:
	a,b = map(int,raw_input().split())
	if a == 0: break
	block = [map(int,raw_input().split()) for i in range(input())]
	road = [[0]*(a+1) for i in range(b+1)]
	road[1][1] = 1
	for bi in range(1,b+1):
		for ai in range(1,a+1):
			if [ai,bi] not in block:
				road[bi][ai] += road[bi-1][ai] + road[bi][ai-1]
	print road[b][a]

Submission status: Accepted

Solution code:
def main():
    while True:
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            break
        dp = [[0] * a for _ in range(b)]
        n = int(input())
        for i in range(n):
            x, y = map(int, input().split())
            dp[y - 1][x - 1] = -1
        dp[0][0] = 1
        for i in range(a):
            for j in range(b):
                if dp[j][i] == -1:
                    continue
                if dp[j - 1][i] != -1:
                    dp[j][i] += dp[j - 1][i]
                if dp[j][i - 1] != -1:
                    dp[j][i] += dp[j][i - 1]
        print(dp[b - 1][a - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h=0
w=0
n=0
while 1:
    h,w=map(int,input().split())
    if not h and not w:
      break
    h-=1
    w-=1
    obs=[[1]*(w+1) for i in range(h+1)]
    n=int(input())
    for i in range(n):
        x,y=map(int,input().split())
        obs[x-1][y-1]=0
    dp=[[0]*(w+2) for i in range(h+2)]
    dp[0][0]=obs[0][0]
    for i in range(h+1):
        for j in range(w+1):
            if obs[i][j]:
                dp[i+1][j]+=dp[i][j]
                dp[i][j+1]+=dp[i][j]
    if obs[h][w]:
        print(dp[h][w])
    else:
        print(0)

Submission status: Accepted

Solution code:
while 1:
    a, b = map(int, input().split())
    if a == 0:
        break
    r = [[1 for i in range(a+b-1)] for j in range(a+b-1)]
    n = int(input())
    for i in range(n):
        x, y = map(int, input().split())
        r[x-1][y-1] = 0
    for i in range(1, a+b-1):
        for j in range(i+1):
            if r[j][i-j] == 0:
                continue
            elif j == 0:
                if r[0][i-j-1] == 0:
                    r[j][i - j] = 0
            elif i-j == 0:
                if r[j-1][0] == 0:
                    r[j][i - j] = 0
            else:
                r[j][i-j] = r[j-1][i-j] + r[j][i-j-1]
    print(r[a-1][b-1])

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 y in range(b)] for x in range(a)]
    memo = [[False for y in range(b)] for x in range(a)]
    
    for i in range(n):
        input_x,input_y = map(int, input().split())
        memo[input_x-1][input_y-1] = True #工事中

    dp[0][0] = 1 #(1,1)に到達できる通り数は１
    for x in range(a):
        for y in range(b):
            if memo[x][y]: #工事中なら
                continue
            if (0<=x-1 and x-1<a):
                dp[x][y] += dp[x-1][y]
            if (0<=y-1 and y-1<b):
                dp[x][y] += dp[x][y-1]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
while True:
    a,b=map(int,input().split())
    if a==0 and b==0:
        break
    n=int(input())
    mp=[list(map(int,input().split())) for _ in range(n)]
    table=[[0]*a for _ in range(b)]
    #上下がa横がb
    #色々めんどくさいので、まずは端っこを求める。
    for m in range(a):
        if [m+1,1] in mp:
            break
        table[0][m]=1
    for l in range(b):
        if [1,l+1] in mp:
            break
        table[l][0]=1
    #上のおかげで0を考慮せずに済む
    for i in range(1,b):
        for j in range(1,a):
            if not [j+1,i+1] in mp: 
                table[i][j]=table[i][j-1]+table[i-1][j]
    print(table[b-1][a-1])

Submission status: Accepted

Solution code:
printed_later = []
while True:
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        break
    n = int(input())
    blocked = []
    for _ in range(n):
        blocked.append([int(x) - 1 for x in input().split()])
    route_nums = [[]]
    edge = 1
    for j in range(y):
        if [0, j] in blocked:
            edge = 0
        route_nums[0].append(edge)
    edge = 1
    for i in range(1, x):
        if [i, 0] in blocked:
            edge = 0
        route_nums.append([edge])
        for j in range(1, y):
            if([i, j] in blocked):
                route_nums[i].append(0)
            else:
                route_nums[i].append(route_nums[i - 1][j] +
                                     route_nums[i][j - 1])
    printed_later.append(route_nums[-1][-1])
    #print(route_nums)
for line in printed_later:
    print(line)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
while(True):
    a,b=list(map(int,input().split()))
    if a==0 and b==0:
        break
        
    n=int(input())
    x=[0]*n
    y=[0]*n
    e=[[0]*b for i in range(a)]
    
    for i in range(n):
        x[i],y[i]=list(map(int,input().split()))
        e[x[i]-1][y[i]-1]=1
    p=[[0]*b for i in range(a)]
    p[0][0]=1
    for i in range(a):
        if e[i][0]==0 and p[i-1][0]==1:
            p[i][0]=1 
    for i in range(b):
        if e[0][i]==0 and p[0][i-1]==1:
            p[0][i]=1
    
    for i in range(1,a):
        for j in range(1,b):
            if e[i-1][j]==1:
                u=0
            else:
                u=p[i-1][j]
            if e[i][j-1]==1:
                v=0
            else:
                v=p[i][j-1]
            p[i][j]=u+v
    
    print(p[a-1][b-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
while True:
    a, b = map(int, input().split())
    if a == b == 0:
        break
    
    n = int(input())
    lst = [[1] * (a + 1) for _ in range(b + 1)]
    lst[0] = [0] * (a + 1)
    for y in range(2, b + 1):
        lst[y][0] = 0

    for _ in range(n):
        c = list(map(int, input().split()))
        lst[c[1]][c[0]] = 0

    for x in range(1, a + 1):
        for y in range(1, b + 1):
            if lst[y][x] == 0:
                continue
            lst[y][x] = lst[y - 1][x] + lst[y][x - 1]
    print(lst[b][a])

Submission status: Accepted

Solution code:
# coding: utf-8
while True:
    # a, bの入力
    a, b = map(int, input().split())
    # 終了処理
    if a == 0 and b == 0:
        exit()
    # nおよび工事中の交差点の入力
    n = int(input())
    const = [list(map(int, input().split())) for i in range(n)]
    # 各座標の到達可能経路数をメモする
    memo =[[0, 1] + [0] * (a - 1)] + [[0] + [-1] * a for i in range(b)]
    # 初期位置合わせのための処理
    memo[0][1] = 1
    # 工事中の交差点に行く経路数は0
    for inter in const:
        memo[inter[1]][inter[0]] = 0
    for i in range(1, b + 1):
        for j in range(1, a + 1):
            # 工事中でない場合、その交差点に行く経路数はその西の交差点と南の交差点の経路数の和
            if memo[i][j] == -1:
                memo[i][j] = memo[i - 1][j] + memo[i][j - 1]
    # 交差点(a, b)に行く経路数が求める答えである
    print(memo[b][a])

Submission status: Accepted

Solution code:
while True:
    a, b = map(int, input().split())
    if a == b == 0:
        break
    
    n = int(input())
    mat = [[0 for i in range(a)] for i in range(b)]
    for i in range(n):
        x, y = map(int, input().split())
        mat[y - 1][x - 1] = -1
    mat[0][0] = 1
    
    flag1 = False
    flag2 = False
    for i in range(a):
        for j in range(b):
            if j == 0:
                if mat[j][i] < 0:
                    flag1 = True
                mat[j][i] = 1 if not flag1 else -1
            elif i == 0:
                if mat[j][i] < 0:
                    flag2 = True
                mat[j][i] = 1 if not flag2 else -1
            else:
                if mat[j][i] < 0:
                    continue
                
                if mat[j-1][i] < 0:
                    if mat[j][i-1] < 0:
                        mat[j][i] = -1
                    mat[j][i] = mat[j][i-1]
                else:
                    if mat[j][i-1] < 0:
                        mat[j][i] = mat[j-1][i]
                    else:
                        mat[j][i] = mat[j-1][i] + mat[j][i-1]
    print(mat[b-1][a-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    while True:
        a,b=map(int,input().split())
        if a==0:
            break
        m=int(input())
        xy=[list(map(int,input().split())) for _ in [0]*m]
        memo=[[True]*a for _ in [0]*b]
        for x,y in xy:
            memo[y-1][x-1]=False
        def check(i,j):
            ans=0
            if i+1<b:
                if memo[i+1][j]:
                    ans+=check(i+1,j)
            if j+1<a:
                if memo[i][j+1]:
                    ans+=check(i,j+1)
            if i==b-1 and j==a-1:
                ans=1
            return ans
        print(check(0,0))
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    while True:
        a, b = map(int, input().split())
        if a == 0:
            return
        k = int(input())
        p = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(k)]

        root = [[0 for j in range(a)] for i in range(b)]

        root[0][0] = 1
        for i in range(0, b):
            for j in range(0, a):
                if i == 0 and j == 0:
                    continue
                if (j, i) in p:
                    root[i][j] = 0
                else:
                    root[i][j] = (root[i - 1][j] if i - 1 >= 0 else 0) + (root[i][j - 1] if j - 1 >= 0 else 0)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
while True:
	try:
		a, b = [int(x) for x in input().split()]
		road = [[0 if i == 0 or j == 0 else 1 for j in range(a+1)] for i in range(b+1)]
		closed = [[int(p) for p in input().split()] for _ in range(int(input()))]

		for x, y in closed:
			road[y][x] = 0

		road[0][1] = 0.5
		road[1][0] = 0.5

		for i in range(1, b+1):
			for j in range(1, a+1):
				road[i][j] = (road[i-1][j] + road[i][j-1]) * road[i][j]

		print(int(road[-1][-1]))
	except:
		break

Submission status: Accepted

Solution code:
while 1:
  try:
    a, b = map(int, input().split())
    cross = [[0 for i in range(a + 1)] for j in range(b + 1)]
    n = int(input())
    for i in range(n):
      x_i, y_i = map(int, input().split())
      cross[y_i][x_i] = 1
    for x in range(a + 1):
      for y in range(b + 1):
        if x != 0 and y != 0:
          if cross[y][x] == 1:
            cross[y][x] = 0
          elif x == 1 and y == 1:
            cross[1][1] = 1
          else:
            cross[y][x] = cross[y - 1][x] + cross[y][x - 1]
    print(cross[b][a])
  except:
    break

Submission status: Accepted

Solution code:
while 1:
    wid,ver = input().split()
    wid = int(wid)
    ver = int(ver)
    if wid==0 or ver == 0:
        break 
    n=int(input())
    dis = [[0 for i in range(ver)] for j in range(wid)]
    for i in range(n):
        w,v = input().split()
        w = int(w)
        v = int(v)
        dis[w-1][v-1]=1

    coo = [[0 for i in range(ver)] for j in range(wid)]
    for i in range(wid):
        for j in range(ver):
            if i==0 or j==0:
                coo[0][0]=1
                if i>0:
                    coo[i][0]=coo[i-1][0]
                if j>0:
                    coo[0][j]=coo[0][j-1]
                if dis[i][0]==1:
                    coo[i][0] = 0
                if dis[0][j]==1:
                    coo[0][j] = 0
            else:
                if dis[i][j] == 1:
                    coo[i][j] = 0
                else:
                    coo[i][j] = coo[i-1][j] + coo[i][j-1]
    print(int(coo[wid-1][ver-1]))

Submission status: Accepted

Solution code:
while True:
    try:
        a,b = (lambda row: [int(row[i]) for i in range(len(row))])(input().split())
        n = int(input())
        obstacle = [(lambda row: [int(row[i]) for i in range(len(row))])(input().split()) for __ in range(n)]
        roads = [[0 for __ in range(b+1)] for __ in range(a+1)]
        roads[1][1] = 1
        for i in range(1,a+1):
            for j in range(1,b+1):
                if not [i,j] in obstacle:
                    roads[i][j] += roads[i-1][j] + roads[i][j-1]
        
        print(str(roads[a][b]))
        
    except:
        break

Submission status: Accepted

Solution code:
while 1:
    try:
        a,b=map(int,input().split())
        root=[[-1 for i in range(a+1)] for j in range(b+1)]
        for i in range(a+1):
            root[0][i]=0
        for i in range(b+1):
            root[i][0]=0
        root[1][1]=1
        for xx in range(int(input())):
            x,y=map(int,input().split())
            root[y][x]=0
        for n in range(3,a+b+3):
            for i in range(1,a+1):
                if 0 < n-i < b+1:
                    if root[n-i][i]==0:continue
                    else:
                        root[n-i][i]=root[n-i][i-1]+root[n-i-1][i] 
        print(root[-1][-1])
    except:break

Submission status: Accepted

Solution code:
while True:
    a, b = [int(x) for x in input().split()]
    if a | b == 0:
        break

    n = int(input())

    dp = [
        [0] * (b + 1)
        for x in range(a + 1)
    ]
    dp[0][1] = 1

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

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

    print(dp[a][b])

Submission status: Accepted

Solution code:
while True:
    x,y = map(int,input().split())
    if(x == 0): break

    n = int(input())
    kouji = [[False for i in range(x+1)] for j in range(y+1)]

    for i in range(n):
        xx,yy = map(int,input().split())
        kouji[yy][xx] = True
    dp = [[0 for i in range(x+1)] for j in range(y+1)]

    dp[1][1] = 1

    for i in range(1,y+1):
        for j in range(1,x+1):
            if (i == 1) and (j == 1) : continue
            if kouji[i][j] : 
                continue
            dp[i][j] = dp[i][j-1]+dp[i-1][j]

    print(dp[y][x])

Submission status: Accepted

Solution code:
def fill(i,j):
    global Map
    for di,dj in move:
        if 0 <= i+di < a and 0 <= j+dj < b and not Map[i+di][j+dj] == '#':
            Map[i+di][j+dj] += 1
            fill(i+di,j+dj)

move = [(1,0),(0,1)]
while True:
    a,b = map(int,input().split())
    if (a,b) == (0,0):
        break
    Map = [[0]*b for _ in range(a)]
    n = int(input())
    objects = []
    for _ in range(n):
        objects.append(tuple(map(int,input().split())))
    for i,j in objects:
        Map[i-1][j-1] = '#'
    fill(0,0)
    print(Map[a-1][b-1])

Submission status: Runtime Error

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):
    #t
    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]):
            #*?&k??WfDO
                if i == 0 :
                    #j
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #?LjD
                        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: Runtime Error

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):
    #t
    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]):
            #*?&k??WfDO
                if i == 0 :
                    #j
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #?LjD
                        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: Runtime Error

Solution code:
p = [[0 for i in xrange(16)] for j in xrange(16)]
while 1:
    a,b = map(int, raw_input().split())
    if a==b==0: break
    n = input()
    for i in xrange(b):
        for j in xrange(a):
            p[i][j] = 0
    for i in xrange(n):
        x,y = map(int, raw_input().split())
        p[y-1][x-1] = -10**6
    p[0][0] = 1
    for i in xrange(b):
        for j in xrange(a):
            if p[i][j]<0: continue
            p[i+1][j] += p[i][j]; p[i][j+1] += p[i][j];
    print p[b-1][a-1]