广度优先搜索 和 深度优先搜索

Posted on |

490.The Maze

BFS：首先建立一个队列，并且将start压入队列。每次从队列头部拿出 当前位置 。

  • 如果该位置是destination则直接返回，
  • 否则就看该位置是否还没有被访问，如果没有被访问，就置为已访问，并 将其四个方向上移动可以停靠的点加入队列。
  • 如果队列都空了还没有发现可以到达的路径，那么就说明无法到达了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def hasPath(self, maze, start, destination):
        """
        :type maze: List[List[int]]
        :type start: List[int]
        :type destination: List[int]
        :rtype: bool
        """
        queue=[start]
        m,n=len(maze),len(maze[0])
        dir=[(1,0),(-1,0),(0,1),(0,-1)]
        while queue:
            i,j=queue.pop(0)

            # 记录当前位置为已访问
            maze[i][j]=-1
            if i==destination[0] and j==destination[1]:
                return True
            for x,y in dir:
                row=i+x
                col=j+y
                # move until the wall
                while 0<=row<m and 0<=col<n and maze[row][col]!=1:
                    row+=x
                    col+=y
                # move back a step
                row-=x
                col-=y
                # 将其四个方向上移动可以停靠的点加入队列
                if maze[row][col]==0 and [row,col] not in queue:
                    queue.append([row,col])
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def hasPath(self, maze, start, destination):
        """
        :type maze: List[List[int]]
        :type start: List[int]
        :type destination: List[int]
        :rtype: bool
        """
        queue=[start]
        m,n=len(maze),len(maze[0])
        visited=[[0 for _ in range(n)] for _ in range(m)]
        visited[start[0]][start[1]]=True
        dir=[(1,0),(-1,0),(0,1),(0,-1)]

        while queue:
            i,j=queue.pop(0)
            if i==destination[0] and j==destination[1]:
                return True
            for x,y in dir:
                row=x+i
                col=y+j
                # move until the wall
                while 0<=row<m and 0<=col<n and maze[row][col]!=1:
                    row+=x
                    col+=y
                # move back a step
                row-=x
                col-=y

                if not visited[row][col]:
                    visited[row][col]=True
                    queue.append([row,col])
        return False

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution(object):
    def hasPath(self, maze, start, destination):
        """
        :type maze: List[List[int]]
        :type start: List[int]
        :type destination: List[int]
        :rtype: bool
        """
        if not maze or len(maze)==0 or len(maze[0])==0:
            return False
        visited=[[False for _ in range(len(maze))] for _ in range(len(maze[0]))]
        return self.dfs(maze, start[0], start[1], destination, visited)

    def dfs(self, maze, i, j, destination, visited):
        # if arrive at the destination, return True
        if i==destination[0] and j==destination[1]:
            return True
        # if the maze[i][j] has been visited, return False
        if visited[i][j]:
            return False

        # Except the above situations, vissited the maze[i][j],
        # and set visited[i][j]=True
        visited[i][j]=True

        # try to four different directions to got the destination
        m,n=len(maze),len(maze[0])
        dir=[(1,0),(-1,0),(0,1),(0,-1)]
        for x,y in dir:
            row=x+i
            col=y+j
            while 0<=row<m and 0<=col<n and maze[row][col]!=1:
                row+=x
                col+=y
            row-=x
            col-=y
            # if any direction can arrive at the destination,return True
            if self.dfs(maze,row,col,destination,visited):
                return True
        return False