資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告