python马丁quiz7

QUIZ 7
COMP9021 PRINCIPLES OF PROGRAMMING
$ python3 quiz_7.py

Enter four integers: 0 2 2 8
Here is the grid that has been generated:
1 1 0 1 1 1 1 1
1 0 0 1 0 0 1 0
Enter four integers: 3 0 4 1
Will compute the number of good paths from (3, 0) to (4, 1)...
There is no good path.
$ python3 quiz_7.py

Enter four integers: 0 2 5 5
Here is the grid that has been generated:
1 1 0 1 1
1 1 1 1 0
0 1 0 0 1
0 1 0 0 1
1 0 1 1 1
Enter four integers: 0 0 4 4
Will compute the number of good paths from (0, 0) to (4, 4)...
There is no good path.
$ python3 quiz_7.py

Enter four integers: 0 100 1 10
Here is the grid that has been generated:
1 1 1 1 1 1 1 1 1 1
Enter four integers: 2 0 4 0
Will compute the number of good paths from (2, 0) to (4, 0)...
There is a unique good path.
$ python3 quiz_7.py

Enter four integers: 0 100 1 10
Here is the grid that has been generated:
1 1 1 1 1 1 1 1 1 1
Enter four integers: 2 0 5 0
Will compute the number of good paths from (2, 0) to (5, 0)...
There is no good path.
$ python3 quiz_7.py

Enter four integers: 0 3 3 4
Here is the grid that has been generated:
1 1 0 1
1 1 1 1
1 1 1 0
Enter four integers: 1 0 2 1
Will compute the number of good paths from (1, 0) to (2, 1)...
There are 7 good paths.
Date: Trimester 1, 2019.
2 COMP9021 PRINCIPLES OF PROGRAMMING
$ python3 quiz_7.py

Enter four integers: 0 3 3 4
Here is the grid that has been generated:
1 1 0 1
1 1 1 1
1 1 1 0
Enter four integers: 1 0 3 1
Will compute the number of good paths from (1, 0) to (3, 1)...
There are 6 good paths.
$ python3 quiz_7.py

Enter four integers: 0 4 6 5
Here is the grid that has been generated:
1 1 0 1 1
1 1 1 1 1
1 1 1 0 1
1 1 0 0 1
1 0 1 1 1
1 1 1 1 0
Enter four integers: 0 0 3 5
Will compute the number of good paths from (0, 0) to (3, 5)...
There are 5 good paths.
$ python3 quiz_7.py

Enter four integers: 0 6 12 4
Here is the grid that has been generated:
1 1 0 1
1 1 1 1
1 1 1 1
1 1 1 1
0 1 1 1
1 1 1 1
0 1 0 1
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 0
1 0 0 1
Enter four integers: 1 0 2 10
Will compute the number of good paths from (1, 0) to (2, 10)...
There are 3979 good paths.

from collections import namedtuple
import numpy as np
from random import seed, randrange
import sys

Point = namedtuple('Point', 'x y')


def display_grid():
    for row in grid:
        print('   ', ' '.join(str(int(e)) for e in row))


def valid(pt):
    return 0 <= pt.x < width and 0 <= pt.y < height


next_step = [[0, -1], [-1, 0], [0, 1], [1, 0]]#up,left,down,right
path_nb = 0
last_steps = [-4, -3]


def nb_of_good_paths(pt_1, pt_2):#!!!y is x ,x is y =O=
    # last_step_times=[(-1,-1),0]
    global path_nb
    #print(path_nb)
    if pt_1 == pt_2:
        # for i in footprint:
        #     print(*i)
        # print()
        # print(last_steps)
        path_nb = path_nb + 1
        # print(grid)
        return
    for i in range(4):
        # print('i',i)
        #print(next_step[i])
        next_pt = Point(pt_1.x + next_step[i][0], pt_1.y + next_step[i][1])
        if next_pt.x < 0 or next_pt.y < 0 or next_pt.x >= len(grid[0]) or next_pt.y >= len(grid) :
            # print(last_steps[-2],last_steps[-1],next_pt)
            #print(next_pt,last_steps[-2],last_steps[-1])
            # if i==next_step[-1]:
            #     return                
            continue    
        if last_steps[-2] ==last_steps[-1] and i==last_steps[-1]:
            continue
            
        #print(next_pt)
        if footprint[next_pt.y][next_pt.x] == 0 and grid[next_pt.y][next_pt.x]:
            # print(next_pt,next_step[i],i)
            #print(next_pt.x,next_pt.y)
            #last_steps.pop(0)
            last_steps.append(i)
            
            footprint[next_pt.y][next_pt.x] = 1
            
            nb_of_good_paths(next_pt, pt_2)          
            footprint[next_pt.y][next_pt.x] = 0
            last_steps.pop()
    
    return path_nb

try:
    for_seed, density, height, width = (abs(int(i)) for i in
                                        input('Enter four integers: ').split()
                                        )
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
if not density:
    density = 1
seed(for_seed)
grid = np.array([randrange(density) > 0
                 for _ in range(height * width)
                 ]
                ).reshape((height, width))
print('Here is the grid that has been generated:')
display_grid()

try:
    i1, j1, i2, j2 = (int(i) for i in input('Enter four integers: ').split())
    pt_1 = Point(i1, j1)
    pt_2 = Point(i2, j2)
    if not valid(pt_1) or not valid(pt_2):
        raise ValueError
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
print('Will compute the number of good paths '
      f'from ({pt_1.x}, {pt_1.y}) to ({pt_2.x}, {pt_2.y})...'
      )

footprint = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
footprint[pt_1.y][pt_1.x] = 1
paths_nb = nb_of_good_paths(pt_1, pt_2)
if not paths_nb:
    print('There is no good path.')
elif paths_nb == 1:
    print('There is a unique good path.')
else:
    print('There are', paths_nb, 'good paths.')