DP-LeetCode361. 轰炸敌人

标签: 动态规划  

1、题目描述

给你一个二维的网格图,网格图中的每一个格子里要么是一堵墙 'W' ,要么是一个敌人 'E' ,要么是一个空位 '0' (数字 0 ),返回你用一个炸弹最多能杀死敌人的数量。

由于墙体足够坚硬,炸弹的威慑力没有办法穿越墙体,所以炸弹只能把所在位置同一行和同一列所有没被墙挡住的敌人给炸死。

注意:你只能把炸弹放在一个空的格子里

2、代码详解

class Solution:
    def maxKilledEnemies(self, grid):
        # init
        if not grid or len(grid) == 0 or len(grid[0]) == 0:
            return 0
        row, col = len(grid), len(grid[0])
        # init
        up = [[0] * col for _ in range(row)]
        down = [[0] * col for _ in range(row)]
        left = [[0] * col for _ in range(row)]
        right = [[0] * col for _ in range(row)]
        # up:从上到下
        for i in range(row):
            for j in range(col):
                if grid[i][j] != 'W':
                    if grid[i][j] == 'E':
                        up[i][j] = 1
                    if i > 0:
                        up[i][j] += up[i - 1][j]
        # down:从下到上
        for i in range(row - 1, -1, -1):
            for j in range(col):
                if grid[i][j] != 'W':
                    if grid[i][j] == 'E':
                        down[i][j] = 1
                    if i + 1 < row:
                        down[i][j] += down[i + 1][j]
        # right:从右到左
        for i in range(row):
            for j in range(col - 1, -1, -1):
                if grid[i][j] != 'W':
                    if grid[i][j] == 'E':
                        right[i][j] = 1
                    if j + 1 < col:
                        right[i][j] += right[i][j + 1]

        # left:从左到右
        for i in range(row):
            for j in range(col):
                if grid[i][j] != 'W':
                    if grid[i][j] == 'E':
                        left[i][j] = 1
                    if j > 0:
                        left[i][j] += left[i][j - 1]

        # sum
        res = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '0':  # 找空地
                    res = max(res, up[i][j] + down[i][j] + left[i][j] + right[i][j])

        return res

grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]  # 在位置 (1,1) 放置炸弹可以杀死 3 个敌人。
s = Solution()
print(s.maxKilledEnemies(grid))

https://blog.csdn.net/qq_32424059/article/details/90415006

版权声明:本文为IOT_victor原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/IOT_victor/article/details/106818802

智能推荐

memmove函数与memcpy函数的模拟实现

memmove函数和memcpy函数都是在内存复制任意类型的,但是它俩也有区别。当源区域和目标区域有重复的,memmove函数会复制缓冲区重叠的部分,而memcpy相反,会报出未知错误。 下面给出两个函数的实现 首先,memmove函数。 实现的基本原理如下图。 具体代码如下: memcpy函数的实现很简单,就直接给出源代码了...

SpringFramework核心 - IOC容器的实现 - 总结

1. 概述 把Spring技术内幕第一章和第二章过了一遍,也做了一些笔记, 对IOC容器的实现有了一定皮毛理解,现在跟着源码再过一遍总结一下IOC容器的初始化,Bean的初始化的过程,做一下总结 ① IOC容器和简单工厂模式 在开始之前,先想想我们平时是怎么使用IOC容器为我们管理Bean的,假设我们要把下面的User类交给IOC容器管理 我们不想关心如何创建一个User对象实例的,仅仅在需要他的...

Python和Django的安装

个人博客导航页(点击右侧链接即可打开个人博客):大牛带你入门技术栈  一、下载并安装Python Python 官方下载地址:http://www.python.org/ftp/python/ 我们这里选择的是 Python 2.7.2 。虽然目前最新版是Python 3.2.2, 但是Django目前还不支持 Python 3.2.2。 安装步骤很简单,双击安装包开...

OpenStack代码贡献初体验

为什么80%的码农都做不了架构师?>>>     OpenStack如今已成为开源云平台中的明星项目,得到广泛关注。OpenStack的优秀出众依赖于众多开发者的努力,在享受其带来的便利与快捷的同时,为其做一份贡献也是一个开发者的义务。  在前段时间的OpenStack的测试过程中,我发现Nova项目中的一个Bug,于是向社区提交了Bug报...

猜你喜欢

SQL Server之8:sql查询每个学生得分最高的两门课

这是一道面试题,今天有空把它记下来,以后遇到此类问题作个参考!刚一看到这个题目,估计好多人都会想到关键字top,其实这里用到的关键字是partition, 好了,先看看表结构,及数据吧!     接下来看一看partition的功能,执行语句   结果如下:   到这里一目了然知道最终结果了!   View Code     &...

vue-video-player 浏览器缩放

文章目录 前言 一、vue-video-player的封装 二、调用 1. 引入 2. vue template代码 2. 主要js代码 效果 前言 此篇是在上一次《[Vue 播放rtmp直播流]》基础之上的更新及补充;近期接到客户需求,需要在视频流上显示额外的信息;当然,视频流上叠加信息可以通过canvas来完成(透明canvas实现),但是在测试的过程中发现,当浏览器缩放时,叠加的图层信息与初...

Hibernate简单实例:数据库驱动配置及数据的输入

前言:本次使用的hibernate框架为idea自动创建的版本:5.3.7.Final   本机的mysql版本为 8.0.11  下载的mysql 驱动程序版本为 mysql-connector-java-8.0.11.jar 一、Hibernate开发的环境搭建 1.使用idea工具创建hibernate项目 然后一路next,按照自己的需要填写项目名称,项目存放...

K8S最小调度单位Pod详解

k8s里面非常重要的一个概念pod,首先简单的介绍是pod是k8s最小的调度单位,一个pod里面可以包含一个或者多个container,一个pod共享一个namespace,它们之前可以通过localhost来进行通信。 docker:Namespace 做隔离,Cgroups 做限制,rootfs做文件系统。 容器本质是进程,而k8s是操作系统。 pod就是类似于进程组。 部署的一些应用有着类似...

实战:Gitlab的搭建以及网站托管的使用方法(一)

实战:Gitlab的搭建以及网站托管的使用方法!(一) gitlab搭建之gitlab标准版本安装 下一期预告:gitlab搭建之***本** 学习之前我们先来看一下我们的学习素材: 链接:https://pan.baidu.com/s/1CgZULZv1EuUmCxmtCAwOpw 提取码:Gitl 前期注意事项: 1、把物理内存调到6G,不然后安装时,会内存太低报错。 (建议使用虚拟机,服务器...