十字绣

题目

• 题目背景

  • 考古学家发现了一块布，布上做有针线活，叫做“十字绣”，即交替地在布的两面穿线。

• 题目描述

  • 布是一个n*m的网格，线只能在网格的顶点处才能从布的一面穿到另一面。每一段线都覆盖一个单位网格的两条对角线之一，而在绣的过程中，一针中连续的两段线必须分处布的两面。给出布两面的图案(实线代表该处有线,虚线代表背面有线)，问最少需要几针才能绣出来？一针是指针不离开布的一次绣花过程。

• 输入格式

  • 第1行两个数N和M(\(1\leq N, M \leq 200\))。

  • 接下来N行每行M个数描述正面。

  • 再接下来N行每行M个数描述反面。

  • 每个格子用.（表示空）,/（表示从右上角连到左下角）,\（表示从左上角连到右下角）和X（表示连两条对角线）表示

• 输出格式

  • 一个数，最少要用的针数。

Solve

• 题意

  给出一个十字绣正反两面，一针中连续的俩段必须处于不同的面，求最少需要多少针可以缝出给出的十字绣。（多少针可以理解为多少根线）

• 解释一下样例：

1. 背面最右面的是一针
2. 背面左下的是一针
3. 和第二针挨着的是一针
4. 剩下三段线的可以一针穿过

• 分析

  • 这道题给出很多段线，问最少的针数，容易想到要求联通块

  • 要想一针穿成，肯定是在一个联通块中，但在一个联通块中却不一定是一针穿成。这怎么理解呢？

  • 就是说一个点已经有了一条正面的线和一条反面的线，在来一条线的话就不能接这根线上了，需要另外一条新的线。那怎么求一个联通块最少用几条线呢？

  • 我们这样想，一条线有两个端点（常识），如果一个点正面的线的段数等于反面的，那这里就没有端点。

  • 这样，一个点的端点数就是在正面的线的段数与反面的差的绝对值，把一个联通块的所有点的这个绝对值加起来除以2就是这个联通块的结果了，要除以二就是因为前面提到了，一根线有两个端点，会算重。

  • 还有一种情况，就是说整个联通块构成一个环，最后计算出来的s是0,但还是需要一根线，所以特判一下就好了。

  • 求联通块的一般方法是并查集，但已经有大佬写了，我这里就分享一下DFS的写法。

• 需要注意以下几点

1. 题目给出的\(n\times m\)是格子数，处理的时候是处理格点，格点总数为\(\left ( n+1 \right ) \times \left ( m+1 \right )\).
2. 题目中表示左上到右下的''在C++语言中是转义字符，判断的时候写为'\\'才能表示'\'，不然会一直编译错误。

• 具体看代码注释（如果看不懂三目运算符可以看后面的注释，是等价的）

Code（早期）

#include <cmath>
#include <cstdio>
using namespace std;
const int N = 205;
struct side {
    int t, next;
}e[N*N<<3];
//存边数组要开8倍，考虑全是X的情况
int head[N*N], tot, f[N*N], face[N*N], rear[N*N];
void add(int x, int y, int z) {
    f[x] = 1;//标记是否有线
    e[++tot].next = head[x];
    head[x] = tot;
    e[tot].t = y;
    z == 1 ? face[x]++ : rear[x]++;
    /*f (z == 1) face[x]++;
    else rear[x]++;*/
    //记录正反面边的个数
    //1表示正面，-1表示反面
}
int n, m, h[N][N], v[N*N], s, ans;
char c[N];
void add1(int x, int y, int k) {//从右上到左下建边
    add(h[x][y+1], h[x+1][y], k);
    add(h[x+1][y], h[x][y+1], k);
}
void add2(int x, int y, int k) {//从左上到右下建边
    add(h[x][y], h[x+1][y+1], k);
    add(h[x+1][y+1], h[x][y], k);
}
void dfs(int x) {
    v[x] = 1;//标记已访问
    s += abs(face[x] - rear[x]);//计算端点数
    for (int i = head[x]; i; i = e[i].next) 
        if (!v[e[i].t]) dfs(e[i].t);
}
void init() {//初始化编号
    for (int i = 1; i <= n+1; i++)
        for (int j = 1; j <= m+1; j++)
            h[i][j] = (i-1) * (m+1) + j;
}
void read(int k) {
    for (int i = 1; i <= n; i++) {
        scanf("%s", c+1);
        for (int j = 1; j <= m; j++)
            if (c[j] == 'X') add1(i, j, k), add2(i, j, k);
            else if (c[j] == '/') add1(i, j, k);
            else if (c[j] == '\\') add2(i, j, k);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    init();
    read(1);//读入正面
    read(-1);//读入背面
    for (int i = 1; i <= n+1; i++)
        for (int j = 1; j <= m+1; j++) {
            int x = h[i][j];
            if (!f[x] || v[x]) continue;
            s = 0;
            dfs(x);
            ans += s ? s >> 1 : 1;
            /*if (s != 0) ans += s >> 1;
            else ans++;*/
        }
    printf("%d\n", ans);
    return 0;
}

Code（后期）

#include <cstdio>

const int N = 205;

struct Edge {
    int next, t;
}e[N*N<<3];
int head[N*N], edc, s[N*N], g;

void Add(int x, int y) {
    e[++edc] = (Edge) {head[x], y};
    head[x] = edc;
    s[x] += g;
}

int n, m, h[N][N], hc, sum, ans;
bool v[N*N];
char c[N];

int Read() {
    for (int i = 1; i < n; ++i) {
        scanf("%s", c + 1);
        for (int j = 1; j < m; ++j) {
            if (c[j] == 'X' || c[j] == '\\') {
                Add(h[i][j], h[i+1][j+1]);
                Add(h[i+1][j+1], h[i][j]);
            }
            if (c[j] == 'X' || c[j] == '/') {
                Add(h[i][j+1], h[i+1][j]);
                Add(h[i+1][j], h[i][j+1]);
            }
        }
    }
}

void Dfs(int x) {
    v[x] = 1;
    sum += s[x] > 0 ? s[x] : -s[x];
    for (int i = head[x]; i; i = e[i].next)
        if (!v[e[i].t]) Dfs(e[i].t);
}

int main() {
    //freopen("stitch.in", "r", stdin);
    //freopen("stitch.out", "w", stdout);
    scanf("%d%d", &n, &m);
    n++; m++;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            h[i][j] = ++hc;
    g = 1; Read();
    g = -1; Read();
    for (int x = 1; x <= n * m; ++x) {
        if (!head[x] || v[x]) continue;
        sum = 0;
        Dfs(x);
        ans += sum ? sum >> 1 : 1;
    }
    printf("%d\n", ans);
    return 0;
}