1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
int T, t, lg2[257], cb[512];
array<array<short, 9>, 9> vis;
vector<pair<int, int>> q;
inline bool tb(short x, int i) { return x & 1 << i; }
inline bool rb(short &x, int i) { return tb(x, i) ? x &= ~(1 << i), true : false;}
bool setvis(int r, int c, int val) {
    if (!tb(vis[r][c], val)) return false;
    vis[r][c] = 1 << val;
    int ro = r / 3 * 3, co = c / 3 * 3;
    REP(i, 9) {
        if (i != c && rb(vis[r][i], val) && (cb[vis[r][i]] == 0 || cb[vis[r][i]] == 1 && !setvis(r, i, lg2[vis[r][i]]))) return false;
        if (i != r && rb(vis[i][c], val) && (cb[vis[i][c]] == 0 || cb[vis[i][c]] == 1 && !setvis(i, c, lg2[vis[i][c]]))) return false;
        int rr = ro + i / 3, cc = co + i % 3;
        if ((rr != r || cc != c) && rb(vis[rr][cc], val) && (cb[vis[rr][cc]] == 0 || cb[vis[rr][cc]] == 1 && !setvis(rr, cc, lg2[vis[rr][cc]]))) return false;
    }
    return true;
}
bool dfs(int i) {
    if (i >= q.size()) return true;
    int r = q[i].first, c = q[i].second;
    if (cb[vis[r][c]] == 1) return dfs(i + 1);
    auto visback = vis;
    for (int x = vis[r][c], lb; x && (lb = x & -x); x -= lb) {
        if (setvis(r, c, lg2[lb]) && dfs(i + 1)) return true;
        vis = visback;
    }
    return false;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX