棋子

题目描述

现有一个 $2$ 行 $n$ 列的棋盘。第 $i$ 行第 $j$ 列表示为 $(i,j)$。在棋盘的第一行有一些己方的棋子，在棋盘第二行有一些敌方的棋子。现在要将己方棋子进行移动，移动规则如下：

• 如果一个己方棋子 $(1,j)$ 正下方 $(2,j)$ 没有其他棋子，则可以将其移动至正下方。

• 如果一个己方棋子 $(1,j)$ 左下 $(2,j-1)$ 或右下 $(2,j+1)$ 有敌方棋子，则可以将其移动至那个有敌方棋子的格子，同时敌方棋子消失。

现在要将己方棋子进行若干次移动，使得有最多的己方棋子到达第二行。（敌方棋子不会移动，只会被己方吃掉）

输入

第一行为棋盘大小 $n$

第 $2-3$ 行为 $2\times n$ 的棋盘

$1$ 表示己方棋子，$2$ 表示敌方棋子，$0$ 表示没有棋子

数据保证己方棋子都在第一行，敌方棋都在第二行

输出

输出最多有多少个己方棋子可以到达第二行

输入样例

5
0 1 1 0 1
2 0 2 2 2

输出样例

2

算法

经典二分图的最大匹配问题

时间复杂度

$O(n^2)$

代码

#include <iostream>
#include <cstring>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1e2 + 5;

int n;
int g[3][N];
bool st[3][N];
PII match[3][N];

bool find(int x, int y)
{
    int dx[3] = {1, 1, 1}, dy[3] = {-1, 0, 1}, s[3] = {2, 0, 2};
    for(int i = 0; i < 3; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(b >= 1 && b <= n && g[a][b] == s[i] && !st[a][b])
        {
            st[a][b] = true;
            PII t = match[a][b];
            if(t.x == 0 || find(t.x, t.y))
            {
                match[a][b] = {x, y};
                return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= 2; i ++)
        for(int j = 1; j <= n; j ++)
            scanf("%d", &g[i][j]);

    int res = 0;
    for(int i = 1; i <= n; i ++)
        if(g[1][i] == 1)
        {
            memset(st, 0, sizeof st);
            if(find(1, i))
                res ++;
        }

    cout << res << endl;
    return 0;
}