Tag: Bitmask

题目描述

There is a rectangular area containing $n \times m$ cells. Two cells are marked with “2”, and another two with “3”. Some cells are occupied by obstacles. You should connect the two “2”s and also the two “3”s with non-intersecting lines. Lines can run only vertically or horizontally connecting centers of cells without obstacles.
Lines cannot run on a cell with an obstacle. Only one line can run on a cell at most once. Hence, a line cannot intersect with the other line, nor with itself. Under these constraints, the total length of the two lines should be minimized. The length of a line is defined as the number of cell borders it passes. In particular, a line connecting cells sharing their border has length $1$.
Fig. 1(a) shows an example setting. Fig. 1(b) shows two lines satisfying the constraints above with minimum total length $18$.

题意概述

给定一张$n \times m$的有障碍矩阵，其中恰有两个2和两个3，其余有些格子上有障碍。求分别连接两个2和两个3的两条不相交路径长度之和的最小值。
数据范围：$1 \le n, m \le 9$。

算法分析

插头DP，维护一排插头，令$f_{i, j, s}$表示处理到第$i$行第$j$列的格子且插头的状态为$s$时的最小值，根据当前格子的状态进行相应的转移。

代码

#include <cstdio>
#include <cstring>

void minify(short &a, short b) {
  a > b && (a = b);
}

static const int N = 11;
int rec[1 << 20];
short mp[N][N], f[2][N][1 << 20]; // 0 for no wire, 2 for wire 2, 3 for wire 3

int modify(int s, int p, int v) {
  return (s & ((1 << (p << 1)) - 1)) | (((s >> ((p + 1) << 1) << 2) + v) << (p << 1));
}

int query(int s, int p) {
  return s >> (p << 1) & 3;
}

int main() {
  int n, m, top = 0;
  for (int i = 0; i < 1 << 20; ++ i) {
    for (int j = 0; j < N; ++ j) if (query(i, j) == 1) goto illegal;
    rec[top ++] = i; illegal: ;
  }
  while (scanf("%d%d", &n, &m), n) {
    for (int i = 0; i < n; ++ i)
      for (int j = 0; j < m; ++ j) scanf("%hd", &mp[i][j]);
    int cur = 0; memset(f, 0x3f, sizeof f), f[cur][0][0] = 0;
    for (int i = 0; i < n; ++ i, cur ^= 1) {
      for (int j = 0; j < m; ++ j)
        for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
          if (f[cur][j][k] < 10000) {
            int p = query(k, j), q = query(k, j + 1);
            if (mp[i][j] == 0) {
              if (! p && ! q)
                minify(f[cur][j + 1][k], f[cur][j][k]),
                minify(f[cur][j + 1][modify(modify(k, j, 2), j + 1, 2)], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(modify(k, j, 3), j + 1, 3)], f[cur][j][k] + 1);
              else if (! p ^ ! q)
                minify(f[cur][j + 1][modify(modify(k, j, p + q), j + 1, 0)], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, p + q)], f[cur][j][k] + 1);
              else if (p && p == q)
                minify(f[cur][j + 1][modify(modify(k, j, 0), j + 1, 0)], f[cur][j][k] + 1);
            } else if (mp[i][j] == 1) {
              if (! p && ! q) minify(f[cur][j + 1][k], f[cur][j][k]); 
            } else {
              if (! p && ! q)
                minify(f[cur][j + 1][modify(k, j, mp[i][j])], f[cur][j][k] + 1),
                minify(f[cur][j + 1][modify(k, j + 1, mp[i][j])], f[cur][j][k] + 1);
              else if (p == mp[i][j] && ! q)
                minify(f[cur][j + 1][modify(k, j, 0)], f[cur][j][k] + 1);
              else if (! p && q == mp[i][j])
                minify(f[cur][j + 1][modify(k, j + 1, 0)], f[cur][j][k] + 1);
            }
          }
      for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _])
        if (! query(k, m)) minify(f[cur ^ 1][0][k << 2 & (1 << ((m + 1) << 1)) - 1], f[cur][m][k]);
      for (int j = 0; j <= m; ++ j)
        for (int _ = 0, k = rec[0]; _ < top; k = rec[++ _]) f[cur][j][k] = 16000;
    }
    printf("%d\n", f[cur][0][0] < 10000 ? f[cur][0][0] - 2 : 0);
  }
  return 0;
}

题目描述

Bob really LOVES chocolate. He thinks he never gets enough. Imagine his joy when his parents told him that they would buy him many rectangular chocolate pieces for his birthday. A piece of chocolate is a $2 \times 1$ or $1 \times 2$ rectangle. Bob’s parents also bought him a nice birthday cake, which can be imagined as a matrix having $M$ rows and $N$ columns. Some positions on the cake are occupied by candles, the others are empty. Bob’s parents asked their son to place as many chocolate pieces as he can on the empty squares on the cake, in such a manner that no two chocolate pieces overlap. However, he would like to keep the chocolate pieces to himself. That’s why, he wants to place only a minimal amount of them on the cake and keep the rest. In order not to make Mon and Dad suspicious, Bob wants to place the chocolate pieces in such a way, that no other piece may be placed on the cake (that is, there won’t exist any two adjacent empty squares). Find the minimal number of pieces which need to be placed on the cake, so that they do not overlap and no extra piece may be added.

题意概述

给定一个$M \times N$的网格，其中有些格子是满的。要求用$2 \times 1$和$1 \times 2$两种方块填充空格子，使得不存在两个相邻的空格子。求至少需要多少方块。
数据范围：$1 \le M \le 70, \; 1 \le N \le 7$。

算法分析

令$f_{i, j, k}$表示处理到第$i$行，第$(i-1)$行的状态为$j$且第$i$行的状态为$k$的方案数。转移时要注意判断上下两行是否有相邻的空格子。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

namespace std {
  template <typename T> void maxify(T &a, T b) { b > a && (a = b); }
  template <typename T> void minify(T &a, T b) { b < a && (a = b); }
}

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 80;
  static const int M = 8;
  int n, m, f[2][1 << M][1 << M], mp[N];
  void input() {
    io > n > m;
    for (int i = 1; i <= n; ++ i)
      for (int j = 1; j <= m; ++ j) {
        char c; io > c, (mp[i] <<= 1) += c == '*';
      }
    mp[0] = mp[n + 1] = mp[n + 2] = (1 << m) - 1;
  }
  void init() { memset(f, 0x1f, sizeof f), f[0][mp[0]][mp[1]] = 0; }
  bool check(int s) {
    bool flag = false;
    for (int i = 0; i < m; s >>= 1, ++ i) {
      if (s & 1) flag = false;
      else { if (flag) return false; flag = true; }
    }
    return true;
  }
  void update(int x, int a, int b, int s, int val, int p) {
    if (check(b) && ! ((1 << m) - 1 - a & (1 << m) - 1 - b)) minify(f[x][b][s], val);
    for (int i = p; i < m; ++ i)
      if (! (b & 1 << i)) {
        if (! (s & 1 << i)) update(x, a, b | 1 << i, s | 1 << i, val + 1, i + 1);
        if (i && ! (b & 1 << i - 1)) update(x, a, b | 1 << i | 1 << i - 1, s, val + 1, i + 1);
      }
  }
  void process() {
    int cur = 0;
    for (int i = 1; i <= n + 1; cur ^= 1, ++ i) {
      memset(f[cur ^ 1], 0x1f, sizeof f[cur ^ 1]);
      for (int j = 0; j < 1 << m; ++ j)
        for (int k = 0; k < 1 << m; ++ k)
          if (f[cur][j][k] < 5e8) update(cur ^ 1, j, k, mp[i + 1], f[cur][j][k], 0);
    }
    io < f[cur][(1 << m) - 1][(1 << m) - 1] < '\n';
  }

public:
  void solve() { input(), init(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}

题目描述

The banquet hall of Computer Scientists’ Palace has a rectangular form of the size $M \times N$. It is necessary to lay hardwood floors in the hall. There are wood pieces of two forms:

• rectangles ($2 \times 1$)
• corners (squares $2 \times 2$ without one $1 \times 1$ square)

You have to determine $X$ – the number of ways to cover the banquet hall.
Remarks. The number of pieces is large enough. It is not allowed to leave empty places, or to cover any part of a surface twice, or to saw pieces.

题意概述

有一个$M \times N$的网格，要求用两种方块覆盖它，一种是$2 \times 1$的方块，一种是$2 \times 2$挖去$1 \times 1$的方块。方块可以旋转。求方案数。
数据范围：$1 \le M, N \le 9$。

算法分析

用$f_{i, j}$表示前$(i-1)$行都已填满且第$i$行的状态为$j$的方案数，转移时枚举$j$可以转移到的状态。暴力计算即可发现合法的转移不会太多。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
  static const int N = 11;
  int n, m, f[N][1 << N];
  void input() { io > n > m; }
  void update(int x, int y, int s, int val, int p) {
    if (y == (1 << m) - 1) { f[x][s] += val; return; }
    for (int i = p; i < m; ++ i)
      if (! (y & 1 << i)) {
        if (! (s & 1 << i)) {
          update(x, y | 1 << i, s | 1 << i, val, i + 1);
          if (i && ! (s & 1 << i - 1)) update(x, y | 1 << i, s | 1 << i | 1 << i - 1, val, i + 1);
          if (i < m - 1 && ! (s & 1 << i + 1)) update(x, y | 1 << i, s | 1 << i | 1 << i + 1, val, i + 1);
        }
        if (i < m - 1 && ! (y & 1 << i + 1)) {
          update(x, y | 1 << i | 1 << i + 1, s, val, i + 2);
          if (! (s & 1 << i)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i, val, i + 2);
          if (! (s & 1 << i + 1)) update(x, y | 1 << i | 1 << i + 1, s | 1 << i + 1, val, i + 2);
        }
      }
  }
  void process() {
    f[0][(1 << m) - 1] = 1;
    for (int i = 0; i <= n; ++ i)
      for (int j = 0; j < 1 << m; ++ j)
        if (f[i][j]) update(i + 1, j, 0, f[i][j], 0);
    io < f[n + 1][0] < '\n';
  }

public:
  void solve() { input(), process(); }
} solver;

signed main() {
  solver.solve();
  return 0;
}