2023-01-14：给定一个二维数组 map，代表一个餐厅，其中只有 0、1 两种值 map[i][j] == 0 表示 (i,j) 位置是空座 map[i][j] == 1 表示 (i,j) 位置坐了人 根据防

// SPDX-License-Identifier: MITpragma 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;}

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    }}
// 正式方法// 轮廓线dpfn 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^8fn 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;}