Giáo án điện tử chuyên đề Khoa học máy tính 11 kết nối Bài 16: Thực hành thiết kế thuật toán theo kĩ thuật duyệt quay lui

0 1 1 0 1

0 0 1 1 1

1 0 0 0 1

0 0 1 0 0

1 0 0 0 0

1 1 0 0 0

0 1 1 1 0

0 0 0 1 1

1 def solveMaza(maze,m,n,x,y,sol):

2 if <(x,y) nằm ở vị trí đích và rỗng>:

3 đặt sol[x][y] = 1 #Thiết lập bước đi và kết thúc

4 return True

5 if <ô (x,y) nằm trong mê cung và đang rỗng>:

6 if <ô (x,y) đã từng được đi qua trước đó>:

7 return False

8 Đặt sol[x][y] = 1 #đánh dấu đã đi qua ô này

9 lần lượt thử đi tiếp sang các ô trái, phải, trên, dưới bằng cách gọi đệ quy hàm solMaze()

10 Nếu thành công thì

11 return True

12 #Tới đây quay lui vì các bước đi tiếp ở trên đều thất bại

13 sol[x][y] = 0 #Thiết lập trạng thái trước khi thực hiện Solvemaze()

14 return False

15 else # ô (x,y) nằm ngoài mê cung hoặc là tường

16 return False

11 return True

12 #Tới đây quay lui vì các bước đi tiếp ở trên đều thất bại

13 sol[x][y] = 0 #Thiết lập trạng thái trước khi thực hiện Solvemaze()

14 return False

15 else # ô (x,y) nằm ngoài mê cung hoặc là tường

16 return False

1 maze = mảng được đọc từ tệp maze.inp

2 m, n = số hàng và số cột của maze

3 khởi tạo ma trận sol khích thước giống maze với các phần tử đều bằng 0 để chứa đường đi cần tìm

• Solvemaze(maze, m, n, 0, 0, solve) #gọi hàm solve tìm đường từ vị trí góc trái bên trên
• Thông báo kết quả

1 #Hàm readmaze/writemaze để đọc/ghi mê cung

2 def readmaze():

3 file = open(“maze.inp”)

4 maze = []

5 for row in file:

6 h = [int(x) for x in row.split()]

7 maze.append(h)

8 file.close()

9 return maze

10 def writemaze(outmaze):

11 f = open(“maze.out”, “w”)

12 for i in outmaze:

13 for j in i:

14 print(j,file = f,end=“”)

15 print(file=f)

16 f.close()

17

18 #Hàm đệ quy tìm đường đi trong mê cung theo phương pháp quay lui

19 def solveMaze (maze, m, n, x, y, sol):

20 #Nếu đã đến ô bên phải phía dưới thì đã tìm được đường và kết thúc

21 if x == n – 1 and y == m – 1 and maze [x][y] == 0:

22 sol[x][y] = 1

23 writemaze(sol)

24 return True

25 #Nếu ô x, y này rỗng và chưa từng được đi qua thì tìm đường đi tiếp

26 if x >= 0 and y < n and y>=0 and y < m and maze[x][y] == 0 and sol[x][y] == 0:

27 if sol[x][y] == 1:

28 Return True

29 if solveMaze(maze, m, n, x+1, y, sol):

30 Return True

31 if solveMaze(maze, m, n, x,y+1, sol):

32 Return True

33 if x > 0 and solveMaze(maze, m, n, x-1, y, sol):

34 Return True

35 if y > 0 and solveMaze (maze, m, n, x, y – 1, sol):

36 Return True

37 sol[y][x] = 0 #Mọi hướng đều không đi được nên đánh đầu

38 return False

39 else:

40 return False

41 #Chương trình chính

42 maze = readmaze ()

43 m = len(maze)

44 n = len(maze[0])

45 print(“Kích thước mê cung: “ ,m, “hàng”, n, “cột”)

46 sol = [[for j in range(n)) for i in range(m)]

47 if solveMaze(maze, m, n, 0, 0, sol) == Fale:

48 print(“Không tồn tại đường đi”)

49 else:

50 for i in range(m):

51 for j in range(n):

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

8 file.close()

9 return maze

10 def writemaze(outmaze):

11 f = open(“maze.out”, “w”)

12 for i in outmaze:

13 for j in i:

14 print(j,file = f,end=“”)

15 print(file=f)

16 f.close()

17

18 #Hàm đệ quy tìm đường đi trong mê cung theo phương pháp quay lui

19 def solveMaze (maze, m, n, x, y, sol):

20 #Nếu đã đến ô bên phải phía dưới thì đã tìm được đường và kết thúc

21 if x == n – 1 and y == m – 1 and maze [x][y] == 0:

22 sol[x][y] = 1

23 writemaze(sol)

24 return True

25 #Nếu ô x, y này rỗng và chưa từng được đi qua thì tìm đường đi tiếp

26 if x >= 0 and y < n and y>=0 and y < m and maze[x][y] == 0 and sol[x][y] == 0:

27 if sol[x][y] == 1:

28 Return True

29 if solveMaze(maze, m, n, x+1, y, sol):

30 Return True

31 if solveMaze(maze, m, n, x,y+1, sol):

32 Return True

33 if x > 0 and solveMaze(maze, m, n, x-1, y, sol):

34 Return True

35 if y > 0 and solveMaze (maze, m, n, x, y – 1, sol):

36 Return True

37 sol[y][x] = 0 #Mọi hướng đều không đi được nên đánh đầu

38 return False

39 else:

40 return False

41 #Chương trình chính

42 maze = readmaze ()

43 m = len(maze)

44 n = len(maze[0])

45 print(“Kích thước mê cung: “ ,m, “hàng”, n, “cột”)

46 sol = [[for j in range(n)) for i in range(m)]

47 if solveMaze(maze, m, n, 0, 0, sol) == Fale:

48 print(“Không tồn tại đường đi”)

49 else:

50 for i in range(m):

51 for j in range(n):

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

23 writemaze(sol)

24 return True

25 #Nếu ô x, y này rỗng và chưa từng được đi qua thì tìm đường đi tiếp

26 if x >= 0 and y < n and y>=0 and y < m and maze[x][y] == 0 and sol[x][y] == 0:

27 if sol[x][y] == 1:

28 Return True

29 if solveMaze(maze, m, n, x+1, y, sol):

30 Return True

31 if solveMaze(maze, m, n, x,y+1, sol):

32 Return True

33 if x > 0 and solveMaze(maze, m, n, x-1, y, sol):

34 Return True

35 if y > 0 and solveMaze (maze, m, n, x, y – 1, sol):

36 Return True

37 sol[y][x] = 0 #Mọi hướng đều không đi được nên đánh đầu

38 return False

39 else:

40 return False

41 #Chương trình chính

42 maze = readmaze ()

43 m = len(maze)

44 n = len(maze[0])

45 print(“Kích thước mê cung: “ ,m, “hàng”, n, “cột”)

46 sol = [[for j in range(n)) for i in range(m)]

47 if solveMaze(maze, m, n, 0, 0, sol) == Fale:

48 print(“Không tồn tại đường đi”)

49 else:

50 for i in range(m):

51 for j in range(n):

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

37 sol[y][x] = 0 #Mọi hướng đều không đi được nên đánh đầu

38 return False

39 else:

40 return False

41 #Chương trình chính

42 maze = readmaze ()

43 m = len(maze)

44 n = len(maze[0])

45 print(“Kích thước mê cung: “ ,m, “hàng”, n, “cột”)

46 sol = [[for j in range(n)) for i in range(m)]

47 if solveMaze(maze, m, n, 0, 0, sol) == Fale:

48 print(“Không tồn tại đường đi”)

49 else:

50 for i in range(m):

51 for j in range(n):

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng

52 if maze[i][j] == 1:

53 sol[i][j] = ‘x’ #Đánh dấu x vào các ô tường

54 writemaze (sol)

55 print(“Đường đi khỏi mê cung:”)

56 for i in sol:

57 for j in i:

58 print(str(j) TRI THỨC + “”,end)

59 print() #in kí tự xuống dòng