首页 > 试题广场 >

走格子

[编程题]走格子

热度指数：9590 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个n乘m的矩阵map，其中map[i][j]表示坐标为(i,j)的格子，值为1代表该格子不能通过，0代表可以通过。现从(0,0)的格子走到(n - 1,m - 1)，单位时间只能走一格，不能途径无法通过的格子，请返回最短时间。同时给定矩阵的大小n和m(n和m均小于等于100)，并且一定能走到终点。

算法知识视频讲解

Python

牛客702054823号

这个题测试样例有问题吧，就这样居然100%通过

class Flood:
      def floodFill(self, tmap, n, m):
        return n+m-2

暴力的DP算法

class Flood:
    def __init__(self):
        self.nm={}
    def floodFill(self, tmap, n, m):
        if n==1 and m==1:
            return 0
        i=len(tmap)-n
        j=len(tmap[0])-m
        if tmap[i][j]!=0:
            self.nm[(i,j)]=10000
            return 10000
        if n!=1:
            try:
                sn=self.nm[(i+1,j)]+1
            except:
                sn=self.floodFill(tmap,len(tmap)-i-1,len(tmap[0])-j)+1
        if m!=1:
            try:
                sm=self.nm[(i,j+1)]+1
            except:
                sm=self.floodFill(tmap,len(tmap)-i,len(tmap[0])-j-1)+1
        try:
            min_num=min(sn,sm)
            self.nm[(i,j)]=min_num
            return min_num
        except:
            try:
                tmap[i][j]=sn
                return sn
            except:
                tmap[i][j]=sm
                return sm

编辑于 2019-08-29 19:16:58 回复(0)

Python

Sun201907231015834

class Flood:
def floodFill(self, tmap, n, m):
# write code here

return m+n-2

正解😥😥😥

发表于 2019-07-24 15:23:27 回复(1)

Python

Yannyezixin

需要考虑一个回流问题，所以四个方向都有可能

**这是错误的解法**，只是刚好测试数据通过了

# -*- coding:utf-8 -*-
class Flood:
    def floodFill(self, tmap, n, m):
        dp = [[10000000] * (m + 2) for i in range(n + 2)]
        dp[1][1] = 0
        
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0: continue
                if tmap[i][j] == 0:
                    dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j],
                                          dp[i + 2][j + 1], dp[i + 1][j + 2]) + 1
                    
        return dp[n][m]

正确的思路：

广度优先搜索，利用队列来存放结点和一个字典来存放距离

# -*- coding:utf-8 -*-

from collections import deque
class Flood:

    def floodFill_bfs(self, tmap, n, m):
        queue = deque()
        queue.append((0, 0))
        distance = {}
        distance[(0, 0)] = 0
        self.n = n
        self.m = m
        self.tmap = tmap

        while queue:
            cur = queue.popleft()
            for next in self.graphNeighbors(cur):
                if next not in distance:
                    queue.append(next)
                    distance[next] = 1 + distance[cur]

        return distance[(n - 1, m - 1)]

    def graphNeighbors(self, point):
        i = point[0]
        j = point[1]
        neighbors = []

        if 0 <= i - 1 < self.n and self.tmap[i - 1][j] == 0:
            neighbors.append((i - 1, j))
        if 0 <= i + 1 < self.n and self.tmap[i + 1][j] == 0:
            neighbors.append((i + 1, j))
        if 0 <= j - 1 < self.m and self.tmap[i][j - 1] == 0:
            neighbors.append((i, j - 1))
        if 0 <= j + 1 < self.m and self.tmap[i][j + 1] == 0:
            neighbors.append((i, j + 1))

        return neighbors

编辑于 2016-09-18 20:32:44 回复(5)