1001. 网格照明_2022_02_08

1001. 网格照明

在大小为 n x n 的网格 grid 上,每个单元格都有一盏灯,最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps ,其中 lamps[i] = [row<sub style="display: inline;">i</sub>, col<sub style="display: inline;">i</sub>] 表示 打开 位于 grid[row<sub style="display: inline;">i</sub>][col<sub style="display: inline;">i</sub>] 的灯。即便同一盏灯可能在 lamps 中多次列出,不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态,它将会照亮 自身所在单元格 以及同一 、同一 和两条 对角线 上的 所有其他单元格

另给你一个二维数组 queries ,其中 queries[j] = [row<sub style="display: inline;">j</sub>, col<sub style="display: inline;">j</sub>] 。对于第 j 个查询,如果单元格 [row<sub style="display: inline;">j</sub>, col<sub style="display: inline;">j</sub>] 是被照亮的,则查询结果为 1 ,否则为 0 。在第 j 次查询之后 [按照查询的顺序] ,关闭 位于单元格 grid[row<sub style="display: inline;">j</sub>][col<sub style="display: inline;">j</sub>] 上及相邻 8 个方向上(与单元格 grid[row<sub style="display: inline;">i</sub>][col<sub style="display: inline;">i</sub>] 共享角或边)的任何灯。

返回一个整数数组 ans 作为答案, ans[j] 应等于第 j 次查询 queries[j] 的结果,1 表示照亮,0 表示未照亮。

示例 1:

输入:n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出:[1,0]
解释:最初所有灯都是关闭的。在执行查询之前,打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮(蓝色方框)。该单元格被照亮,所以 ans[0] = 1 。然后,关闭红色方框中的所有灯。

第 1 次查询检查 grid[1][0] 是否被照亮(蓝色方框)。该单元格没有被照亮,所以 ans[1] = 0 。然后,关闭红色矩形中的所有灯。

示例 2:

输入:n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出:[1,1]

示例 3:

输入:n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出:[1,1,0]

提示:

  • 1 <= n <= 10<sup>9</sup>
  • 0 <= lamps.length <= 20000
  • 0 <= queries.length <= 20000
  • lamps[i].length == 2
  • 0 <= row<sub style="display: inline;">i</sub>, col<sub style="display: inline;">i</sub> < n
  • queries[j].length == 2
  • 0 <= row<sub style="display: inline;">j</sub>, col<sub style="display: inline;">j</sub> < n

Solution

理解就是,给定的lamps表示一个灯的序列,该序列中的每个灯所在行和列以及对角线上的灯是亮的,表示这个灯是打开的,并且序列之间的灯导致亮是叠加的,互不干涉,现在需要遍历queries中的位置,每遍历一个灯,就需要把这个位置的灯紧邻的灯都设置为关闭

​// 官方题解,golang练手
func gridIllumination(n int, lamps [][]int, queries [][]int) []int {
    type pair struct {x ,y int}
    points := map[pair]bool{}
    row := map[int]int{}
    col := map[int]int{}
    diagonal := map[int]int{}
    antiDiagonal := map[int]int{}

    for _, lamp := range lamps {
        r,c := lamp[0],lamp[1]
        p := pair{r,c}
        if points[p] {
            continue
        }
        points[p] = true
        row[r]++
        col[c]++
        diagonal[r-c]++
        antiDiagonal[r+c]++
    }

    ans := make([]int, len(queries))
    for i, query := range queries {
        r, c := query[0], query[1]
        if row[r] > 0 || col[c] > 0 || diagonal[r-c] > 0 || antiDiagonal[r+c] > 0 {
            ans[i] = 1
        }
        for x := r - 1; x <= r + 1; x++ {
            for y := c - 1; y <= c + 1; y++ {
                if x < 0 || y < 0 || x >= n || y >= n || !points[pair{x,y}] {
                    continue
                }
                delete(points,  pair{x,y})
                row[x]--
                col[y]--
                diagonal[x-y]--
                antiDiagonal[x+y]--
            }
        }
    }
    return ans
}

本文来自博客园,作者:StimuMing,转载请注明原文链接:https://www.cnblogs.com/fole-del/p/15873128.html

推荐这些文章:

day08-2022-01-08

湖南
day08数据库
一,表单标签
1.其它标签
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
</head>
<body>
<!-- 在网页中加入音频 -->
<audio controls="controls">
<source src="https://www.cnblogs.com/elliottmoo/p/jay.mp3"><...

1725. 可以形成最大正方形的矩形数目_2022_02_04

1725. 可以形成最大正方形的矩形数目
给你一个数组 rectangles ,其中 rectangles[i] = [l<sub style="display: inline;">i</sub>, w<sub style="display: inline;">i</sub>] 表示第 i 个矩形的长度为 l<sub style="display: inline;">i</sub> 、宽度为 w<sub style="display: inline;">i</sub> 。
如果存在 k 同时满足 ...

1706. 球会落何处_2022_02_24

1706. 球会落何处
用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。
箱子中的每个单元格都有一个对角线挡板,跨过单元格的两个角,可以将球导向左侧或者右侧。

将球导向右侧的挡板跨过左上角和右下角,在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角,在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案,或者被一块挡导向到箱子的任意一侧边上,就会卡住。
返回一个大小为 n 的数组 answer ,其中 answer[i] 是球放在顶部的第...

<2022年4月13号>

浮动
竖着排列的项目想横排列
float:left
float:right
浮动作用
1.将块元素变成行内块,将行元素变成行内块
标准文档流:在不使用其他与排列和定位相关的css规则时,各个元素排列方式
脱离(标准)文档流
1.浮动
2.定位
3.弹性盒子
预防浮动带来的问题
1.设置父级,设置好宽高
清除浮动
1.clear:both;在被影响的元素上加
2.给父级设置宽高加display:block
3.给父级设置宽高加overflow:hidden;
4.伪类{宽高,display:block; clear:both; overflow:hidden}

...

YACS 2022年02月月赛 甲组 开关灯

https://iai.sh.cn/problem/589
晚自修摸鱼 15 min 想了出来。
考虑朴素覆盖,显然不行。
换种思路,考虑一个数被多少数覆盖到了,发现 m 很小,直接状压。
\(f[S]\) 表示仅以 S 状态的覆盖到的数的数量,即 \(f[S]\) 贡献的数不能贡献到 \(f[T],T\subseteq S\)。
发现可以容斥,即枚举超集,然后减去即可。
再发现转移顺序可能很奇怪,那么记搜。
注意 int128。
#include <bits/stdc++.h>
#define int __int128
#define il inline
using name...

2022-1-22DFSday4

题1:

200. 岛屿数量

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
 
示例 1:
输入:grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出:1

示例 2:
输入:grid = [
["1","1","0...

2022-02-06 集训题解

排队
link
Desciption

\(n,m\le 10^5\)
Solution
不难注意到的是,我们假设 \(f_i\) 为 \(i\) 之前 \(\le a_i\) 的值的个数,那么我们需要满足:
\[\sum_{i=1}^{n} i-f_i=\sum_{i=1}^{n} i-\min(i,a_i)
\]又因为我们可以知道 \(f_i\le \min(i,a_i)\),所以我们对于每一个 \(i\) 都有 \(f_i=\min(i,a_i)\)。
考虑如何构造这样的 \(a\) 。可以发现,我们选了一个 \(a_i\) 就将 \(a_i\) 这个位置赋值为 \(1\)。那么,\(...

<2022年4月7号>

无序列表
Unordered list
<ul>
  <li></li>
  <li></li>
  <li></li>
</ul>
有序列表
<ol>
  <li></li>
  <li></li>
  <li></li>
</ol>
无序列表默认自带样式
list-style:di...

<2022年4月4号>

换行标签
<br>
分割线
<hr>
 
转义符
空格 一个汉字占两个 
版权信息 © ©
超链接标签
<a href=”#”></a>
#访问当前页面,刷新当前页面
a标签默认打开方式是当前页面打开
Target=”-self”当前页面打开
Target=”-blank”新页面打开
display:inline-block(融合行内于块级)

布局标签

 
表格属性table   tr是行  td是列也叫单元格
属性

width宽度
height高度
表格内外...

mysql>>子串的使用-如排序>>substr

------+表结构
| emp_no | birth_date | first_name | last_name | gender | hire_date |
+--------+------------+------------+-----------+--------+------------+
| 10001 | 1953-09-02 | Georgi | Facello | M | 1986-06-26 |
| 10002 | 1964-06-02 | Bezalel | Simmel | F | 1985-11-21 |
| ...

文章标题:1001. 网格照明_2022_02_08
文章链接:https://www.dianjilingqu.com/50874.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>