数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++程序：求所有被灯照亮的单元格的总和
假设我们有一个H行W列的网格。每个方格都是整洁的或不整洁的。我们可以在这个网格中的零个或多个整洁的方格上放置灯。一个灯可以照亮四个方向（上、下、左、右）的单元格，直到到达网格边缘或第一个不整洁的方格（不整洁的单元格不会被照亮）。灯也会照亮它所在的单元格。如果网格中G[i, j]是'.'，则该单元格是整洁的；如果是'#'，则该单元格是不整洁的。设K为整洁的方格数。共有2^K种放置灯的方法。假设对于这2^K种方法中的每一种，都计算出一个或多个灯照亮的单元格数。我们需要找到这些数字的总和，模10^9 + 7。
因此，如果输入如下所示：
| . | . | # |
| # | . | . |
则输出将是52
步骤
为了解决这个问题，我们将遵循以下步骤：
m := 10^9 + 7 N = 2003 Define 2D arrays u, l, r, d of order N x N, and another list p with N^2 elements. h := row count of matrix w := column count of matrix tidy := 0 p[0] := 1 for initialize i := 1, when i <= h * w, update (increase i by 1), do: p[i] := p[i - 1] * 2 mod m for initialize i := 0, when i < h, update (increase i by 1), do: for initialize j := 0, when j < w, update (increase j by 1), do: u[i, j] := i l[i, j] := j if i is non-zero, then: u[i, j] := u[i - 1, j] if j is non-zero, then: l[i, j] := l[i, j - 1] if matrix[i, j] is same as '#', then: u[i, j] := i + 1 l[i, j] := j + 1 Otherwise (increase tidy by 1) for initialize i := h - 1, when i >= 0, update (decrease i by 1), do: for initialize j := w - 1, when j >= 0, update (decrease j by 1), do: d[i, j] := i r[i, j] := j if i < h - 1, then: d[i, j] := d[i + 1, j] if j < w - 1, then: r[i, j] := r[i, j + 1] if matrix[i, j] is same as '#', then: d[i, j] := i - 1 r[i, j] := j - 1 cnt := 0 for initialize i := 0, when i < h, update (increase i by 1), do: for initialize j := 0, when j < w, update (increase j by 1), do: if matrix[i, j] is same as '#', then: Ignore following part, skip to the next iteration src := d[i, j] + r[i, j] - u[i, j] - l[i, j] + 1 cnt := (cnt + (p[src] - 1) * p[tidy - src]) mod m return cnt
示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7, N = 2003;
int u[N][N], l[N][N], r[N][N], d[N][N], p[N * N];
int solve(vector<vector<char>> matrix){
int h = matrix.size();
int w = matrix[0].size();
int tidy = 0;
p[0] = 1;
for (int i = 1; i <= h * w; ++i)
p[i] = p[i - 1] * 2 % m;
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
u[i][j] = i;
l[i][j] = j;
if (i)
u[i][j] = u[i - 1][j];
if (j)
l[i][j] = l[i][j - 1];
if (matrix[i][j] == '#'){
u[i][j] = i + 1;
l[i][j] = j + 1;
}
else
++tidy;
}
}
for (int i = h - 1; i >= 0; --i){
for (int j = w - 1; j >= 0; --j){
d[i][j] = i;
r[i][j] = j;
if (i < h - 1)
d[i][j] = d[i + 1][j];
if (j < w - 1)
r[i][j] = r[i][j + 1];
if (matrix[i][j] == '#'){
d[i][j] = i - 1;
r[i][j] = j - 1;
}
}
}
int cnt = 0;
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
if (matrix[i][j] == '#')
continue;
int src = d[i][j] + r[i][j] - u[i][j] - l[i][j] + 1;
cnt = (cnt + (p[src] - 1) * p[tidy - src]) % m;
}
}
return cnt;
}
int main(){
vector<vector<char>> matrix = { { '.', '.', '#' }, { '#', '.', '.' } };
cout << solve(matrix) << endl;
}输入
3, 2, { 1, 5, 9 }, { 2, 4, 2 }输出
52
更新于：2022年3月3日
123 次浏览
广告