2023-01-14：给定一个二维数组map，代表一个餐厅，其中只有0、1两种值
map[i][j] == 0 表示(i,j)位置是空座
map[i][j] == 1 表示(i,j)位置坐了人
根据防疫要求，任何人的上、下、左、右，四个相邻的方向都不能再坐人
但是为了餐厅利用的最大化，也许还能在不违反防疫要求的情况下，继续安排人吃饭
请返回还能安排的最大人数
如果一开始的状况已经不合法，直接返回-1
比如:
1 0 0 0
0 0 0 1
不违反防疫要求的情况下，这个餐厅最多还能安排2人，如下所示，X是新安排的人
1 0 X 0
0 X 0 1
再比如:
1 0 0 0 0 1
0 0 0 0 0 0
0 1 0 0 0 1
0 0 0 0 0 0
不违反防疫要求的情况下，这个餐厅最多还能安排7人，如下所示，X是新安排的人
1 0 0 X 0 1
0 0 X 0 X 0
0 1 0 X 0 1
X 0 X 0 X 0
数据范围 : 1 <= 矩阵的行、列 <= 20
来自华为。
答案2023-01-14：
轮廓线dp。
代码用solidity和rust编写。
代码用solidity编写。代码如下：
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;
contract Hello{
function main() public pure returns (int32){
int32[][] memory matrix = new int32[][](2);
for (int32 i = 0; i < 2; i++) {
matrix[uint32(i)] = new int32[](2);
for (int32 j = 0; j < 2; j++) {
matrix[uint32(i)][uint32(j)] = 0;
}
}
//matrix[1][1] = 1;
int32 ans = mostSeats2(matrix);
return ans;
}
// 正式方法
// 轮廓线dp
function mostSeats2(int32[][] memory map) public pure returns(int32){
int32 n = int32(int(map.length));
int32 m = int32(int(map[0].length));
int32[] memory arr = new int32[](uint32(n));
for (int32 i = 0; i < n; i++) {
int32 status = 0;
for (int32 j = 0; j < m; j++) {
if (map[uint32(i)][uint32(j)] == 1) {
if (i > 0 && map[uint32(i - 1)][uint32(j)] == 1) {
return -1;
}
if (j > 0 && map[uint32(i)][uint32(j - 1)] == 1) {
return -1;
}
}
status |= map[uint32(i)][uint32(j)] *leftk(j);
}
arr[uint32(i)] = status;
}
int32 s = leftk(m);
int32[][][] memory dp = new int32[][][](uint32(n));
for (int32 i = 0; i < n; i++) {
dp[uint32(i)] = new int32[][](uint32(m));
for (int32 j = 0; j < m; j++) {
dp[uint32(i)][uint32(j)] = new int32[](uint32(s));
for (int32 k = 0; k < s; k++) {
dp[uint32(i)][uint32(j)][uint32(k)] = -2;
}
}
}
int32 ans = process2(arr, n, m, 0, 0, 0, dp);
return ans == -1 ? int32(0) : ans;
}
// 20 * 20 * 2^20 -> 4 * 10^8
function process2(int32[] memory arr, int32 n, int32 m, int32 i, int32 j, int32 status, int32[][][] memory dp) public pure returns (int32){
if (j == m) {
return process2(arr, n, m, i + 1, 0, status, dp);
}
if (i == n) {
return 0;
}
if (dp[uint32(i)][uint32(j)][uint32(status)] != -2) {
return dp[uint32(i)][uint32(j)][uint32(status)];
}
A memory a = A(0,0,0,0,0,0,0);
a.left = status0(status, j - 1, m);
a.up = status0(status, j, m);
a.cur = status0(arr[uint32(i)], j, m);
a.right = status0(arr[uint32(i)], j + 1, m);
if (a.up == 1 && a.cur == 1) {
return -1;
}
a.p1 = -1;
if (a.cur == 1) {
a.p1 = process2(arr, n, m, i, j + 1, status | leftk(j), dp);
} else {
a.p1 = process2(arr, n, m, i, j + 1, (status | leftk(j)) ^ leftk(j), dp);
}
a.p2 = -1;
if (a.left == 0 && a.up == 0 && a.cur == 0 && a.right == 0) {
int32 next2 = process2(arr, n, m, i, j + 1, status | leftk(j), dp);
if (next2 != -1) {
a.p2 = 1 + next2;
}
}
a.ans = max(a.p1, a.p2);
dp[uint32(i)][uint32(j)][uint32(status)] = a.ans;
return a.ans;
}
function status0(int32 status, int32 i, int32 m)public pure returns (int32) {
return (i < 0 || i == m || (status & (leftk(i))) == 0) ? int32(0) : int32(1);
}
function leftk(int32 k) public pure returns (int32){
int32 ans = 1;
while (k>0){
ans*=2;
k--;
}
return ans;
}
function max(int32 a,int32 b)public pure returns (int32){
if(a>b){
return a;
}else{
return b;
}
}
}
// 局部变量超过了16个，需要用结构体封装
struct A{
int32 left;
int32 up;
int32 cur;
int32 right;
int32 p1;
int32 p2;
int32 ans;
}
代码用rust编写。代码如下：
use rand::Rng;
use std::iter::repeat;
fn main() {
let mut matrix = vec![vec![0, 0], vec![0, 0]];
let ans3 = most_seats2(&mut matrix);
println!("ans3 = {}", ans3);
let nn: i32 = 10;
let mm: i32 = 10;
let one_p = 15;
let test_time: i32 = 10000;
println!("测试开始");
for i in 0..test_time {
let n = rand::thread_rng().gen_range(0, nn) + 1;
let m = rand::thread_rng().gen_range(0, mm) + 1;
let mut matrix = random_matrix(n, m, one_p);
let ans1 = most_seats1(&mut matrix);
let ans2 = most_seats2(&mut matrix);
if ans1 != ans2 {
println!("出错了!{}", i);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
// 为了测试，普通方法
// 普通的状态压缩动态规划
// 每一行用dfs的方法
// 体系学习班，章节44 : 状态压缩的动态规划，贴瓷砖问题类似
fn most_seats1(map: &mut Vec<Vec<i32>>) -> i32 {
let n = map.len() as i32;
let m = map[0].len() as i32;
let mut arr: Vec<i32> = repeat(0).take(n as usize).collect();
for row in 0..n {
let mut status = 0;
let mut col = 0;
let mut i = m - 1;
while col < m {
if map[row as usize][col as usize] == 1 {
if row > 0 && map[(row - 1) as usize][col as usize] == 1 {
return -1;
}
if col > 0 && map[row as usize][(col - 1) as usize] == 1 {
return -1;
}
}
status |= map[row as usize][col as usize] << i;
col += 1;
i -= 1;
}
arr[row as usize] = status;
}
let mut dp: Vec<Vec<i32>> = repeat(repeat(-2).take((1 << m) as usize).collect())
.take(n as usize)
.collect();
let ans = process1(&mut arr, 0, 0, m, &mut dp);
return if ans == -1 { 0 } else { ans };
}
fn process1(arr: &mut Vec<i32>, row: i32, pre: i32, m: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
if row == arr.len() as i32 {
return 0;
}
if dp[row as usize][pre as usize] != -2 {
return dp[row as usize][pre as usize];
}
let cur = arr[row as usize];
let mut ans = 0;
if (cur & pre) != 0 {
ans = -1;
} else {
ans = dfs(arr, row, m - 1, pre, cur, m, dp);
}
dp[row as usize][pre as usize] = ans;
return ans;
}
fn dfs(
arr: &mut Vec<i32>,
row: i32,
col: i32,
pre: i32,
seats: i32,
m: i32,
dp: &mut Vec<Vec<i32>>,
) -> i32 {
if col == -1 {
return process1(arr, row + 1, seats, m, dp);
} else {
let p1 = dfs(arr, row, col - 1, pre, seats, m, dp);
let mut p2 = -1;
if (pre & (1 << col)) == 0
&& (seats & (1 << col)) == 0
&& (col == m - 1 || (seats & (1 << (col + 1))) == 0)
&& (col == 0 || (seats & (1 << (col - 1))) == 0)
{
let next2 = dfs(arr, row, col - 1, pre, seats | (1 << col), m, dp);
if next2 != -1 {
p2 = 1 + next2;
}
}
return get_max(p1, p2);
}
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// 正式方法
// 轮廓线dp
fn most_seats2(map: &mut Vec<Vec<i32>>) -> i32 {
let n = map.len() as i32;
let m = map[0].len() as i32;
let mut arr: Vec<i32> = repeat(0).take(n as usize).collect();
for i in 0..n {
let mut status = 0;
for j in 0..m {
if map[i as usize][j as usize] == 1 {
if i > 0 && map[(i - 1) as usize][j as usize] == 1 {
return -1;
}
if j > 0 && map[i as usize][(j - 1) as usize] == 1 {
return -1;
}
}
status |= map[i as usize][j as usize] << j;
}
arr[i as usize] = status;
}
let s = 1 << m;
let mut dp: Vec<Vec<Vec<i32>>> = repeat(
repeat(repeat(-2).take(s as usize).collect())
.take(m as usize)
.collect(),
)
.take(n as usize)
.collect();
let ans = process2(&mut arr, n, m, 0, 0, 0, &mut dp);
return if ans == -1 { 0 } else { ans };
}
// 20 * 20 * 2^20 -> 4 * 10^8
fn process2(
arr: &mut Vec<i32>,
n: i32,
m: i32,
i: i32,
j: i32,
status: i32,
dp: &mut Vec<Vec<Vec<i32>>>,
) -> i32 {
if j == m {
return process2(arr, n, m, i + 1, 0, status, dp);
}
if i == n {
return 0;
}
if dp[i as usize][j as usize][status as usize] != -2 {
return dp[i as usize][j as usize][status as usize];
}
let left = status0(status, j - 1, m);
let up = status0(status, j, m);
let cur = status0(arr[i as usize], j, m);
let right = status0(arr[i as usize], j + 1, m);
if up == 1 && cur == 1 {
return -1;
}
let mut p1 = -1;
if cur == 1 {
p1 = process2(arr, n, m, i, j + 1, status | (1 << j), dp);
} else {
p1 = process2(arr, n, m, i, j + 1, (status | (1 << j)) ^ (1 << j), dp);
}
let mut p2 = -1;
if left == 0 && up == 0 && cur == 0 && right == 0 {
let next2 = process2(arr, n, m, i, j + 1, status | (1 << j), dp);
if next2 != -1 {
p2 = 1 + next2;
}
}
let ans = get_max(p1, p2);
dp[i as usize][j as usize][status as usize] = ans;
return ans;
}
fn status0(status: i32, i: i32, m: i32) -> i32 {
return if i < 0 || i == m || (status & (1 << i)) == 0 {
0
} else {
1
};
}
fn random_matrix(n: i32, m: i32, p0: i32) -> Vec<Vec<i32>> {
let mut ans: Vec<Vec<i32>> = repeat(repeat(0).take(m as usize).collect())
.take(n as usize)
.collect();
for i in 0..n {
for j in 0..m {
ans[i as usize][j as usize] = if rand::thread_rng().gen_range(0, 100) < p0 {
1
} else {
0
};
}
}
return ans;
}
