A

给定一个3*3的数独矩阵，请你判断这一数独矩阵是一解、多解、还是无解。

数独规则如下：

  1. 每一行中不能有重复数字
  2. 每一列中不能有重复数字
  3. 每一块中不能有重复数字

其中，块是题目中给定的三个坐标。保证每一块中都有三个坐标，一共有三个块。

对于一个3*3的数独矩阵，其左上角坐标是[0,0][0,0]，右下角坐标是[2,2][2,2]

输入

共有T(T≤10)T(T\le 10)组输入，每组输入包含一个3*3的数独矩阵，和三行描述块坐标的信息。
*表示该位置待填充，数字表示该位置已填充对应数字。
每一行中有三个坐标，表示一个块内的坐标，保证坐标位置合法。

输出

如果一解，输出“Unique”，并输出对应解法；
如果多解，输出“Multiple”；
如果无解，输出“No”。

solution

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
const int N = 5;
char a[N][N], ans[N][N];
vector<pair<int, int>> v[4];
int flag;
bool used[5];
bool chk() {
    // line
    rep(i, 1, 3) {
        rep(k, 1, 3) used[k] = 0;
        rep(j, 1, 3) {
            int x = a[i][j] - '0';
            if (used[x]) return 0;
            used[x] = 1;
        }
    }

    // row
    rep(j, 1, 3) {
        rep(k, 1, 3) used[k] = 0;
        rep(i, 1, 3) {
            int x = a[i][j] - '0';
            if (used[x]) return 0;
            used[x] = 1;
        }
    }

    rep(b, 1, 3) {
        rep(k, 1, 3) used[k] = 0;
        for (auto [u, v] : v[b]) {
            int x = a[u][v] - '0';
            if (used[x]) return 0;
            used[x] = 1;
        }
    }
    return 1;
}
vector<pair<int, int>> em;
int len;
void dfs(int p) {
    if (p == len) {
        if (chk()) {
            ++flag;
            rep(i, 1, 3) rep(j, 1, 3) ans[i][j] = a[i][j];
        }
        return;
    }
    if (flag >= 2) return;
    rep(i, 1, 3) {
        int x = em[p].first, y = em[p].second;
        a[x][y] = i + '0';
        dfs(p + 1);
    }
}
void solve() {
    flag = 0;
    em.clear();
    rep(i, 1, 3) cin >> a[i] + 1;
    rep(i, 1, 3) v[i].clear();
    int x, y;
    rep(i, 1, 3) {
        rep(j, 1, 3) {
            cin >> x >> y;
            ++x, ++y;
            v[i].emplace_back(x, y);
            if (a[i][j] == '*') em.emplace_back(i, j);
        }
    }
    len = em.size();
    dfs(0);
    if (flag == 1) {
        cout << "Unique\n";
        rep(i, 1, 3) cout << ans[i] + 1 << '\n';
    } else if (flag == 0)
        cout << "No\n";
    else
        cout << "Multiple\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}
/*

4
*2*
1*2
***
0 0 0 1 1 0
0 2 1 1 1 2
2 0 2 1 2 2
**3
***
***
0 0 1 0 1 1
0 1 0 2 1 2
2 0 2 1 2 2
**3
1**
**2
0 0 1 0 1 1
0 1 0 2 1 2
2 0 2 1 2 2
3*3
1**
**2
0 0 1 0 1 1
0 1 0 2 1 2
2 0 2 1 2 2
*/

B

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
const int N = 55;
char a[N][N];
int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};
int n, m;
char tar;
map<pair<int, int>, int> mp;
int dir;
bool out(int x, int y) { return x < 1 || x > n || y < 1 || y > n; }
void getfar(int x, int y, int i, int &d, int &xx, int &yy) {
    int dep = 0;
    while (!out(x + dx[i], y + dy[i])) {
        // cerr << "far " << i << ' ' << x << ' ' << y<<'\n';
        x += dx[i];
        y += dy[i];
        ++dep;
        if (tar == a[x][y] && dep > d) {
            d = dep;
            // dir = i;
            xx = x, yy = y;
        } else if (a[x][y] != 'b' && a[x][y] != 'w')
            return;
    }
}
void trans(char &tar) {
    if (tar == 'w')
        tar = 'b';
    else
        tar = 'w';
}
int cir;
void op() {
    int x, y;
    cin >> x >> y;
    ++x, ++y;
    a[x][y] = tar;
    trans(tar);
    ++cir;
    rep(i, 0, 7) {
        int dis = 0;
        int xx = x, yy = y;
        getfar(x, y, i, dis, xx, yy);

        if (dis >= 2) {
            int nx = x, ny = y;
            // cout << i << ' ' << xx << ' ' << yy << ' ' << dis << '\n';
            while (x != xx || y != yy) {
                x += dx[i];
                y += dy[i];
                //   cerr<<x<<' '<<y<<endl;
                if (x == xx && y == yy) break;
                if (!(mp.count({x, y}) && mp[{x, y}] == cir - 1)) {
                    //   cerr<<"trans "<<x<<' '<<y<<endl;
                    mp[{x, y}] = cir;
                    trans(a[x][y]);
                }
            }
            x = nx; y = ny;
        }
    }
}
void solve() {
    memset(a, 0, sizeof a);
    mp.clear();
    tar = 'w';
    cir = 0;
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i] + 1;
    while (m--) {
        op();
    }
        rep(i, 1, n) cout << a[i] + 1 << '\n';
    cout << "END\n";
}
int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}
/*
2
6 4
------
---b--
-wwwb-
-bbw--
-ww---
-ww---
1 2
0 2
2 0
2 5
6 4
------
--b---
--wbb-
--www-
--b-b-
--w---
1 4
1 1
5 4
0 2
*/

/*
--b---
--bb--
wbwbwb
-www--
-wb---
-ww---
END
--b---
-bw-w-
--wbw-
--bwb-
--w-w-
--w-w-
END
*/

C

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
const int N = 55;
char g[N][N];
int a[N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
vector<pair<int, int>> E, F;
int flag, n, m, A, B;
int getDis(int x, int y, int xx, int yy) {  // bfs
    return abs(x - xx) + abs(y - yy);
}

void solve() {
    flag = 0;
    cin >> n >> m >> A >> B;
    rep(i, 0, A - 1) cin >> a[i];
    rep(i, 1, n) cin >> g[i] + 1;
    if (A < B) {
        cout << -1 << '\n';
        return;
    }

    rep(i, 1, n) rep(j, 1, m) {
        if (g[i][j] == 'E') {
            E.emplace_back(i, j);
        } else if (isdigit(g[i][j])) {
            F.emplace_back(i, j);
        }
    }
    vector<int> val;
    for (int i = 0; i < E.size(); ++i) val.push_back(INT_MAX);
    for (auto f : F)
        for (int i = 0; i < E.size(); ++i) {
            int x = getDis(f.first, f.second, E[i].first, E[i].second);
            val[i] = min(val[i], x);
        }
    long long ans = 0;
    for (int x : val) ans += x;
    if (ans > INT_MAX)
        cout << -1 << '\n';
    else
        cout << ans << '\n';
}
int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}