| 记录编号 |
602005 |
评测结果 |
WWEEEEEEEEEEEEEEEEEEEEEEE |
| 题目名称 |
3627.[NOIP 2021]棋局 |
最终得分 |
0 |
| 用户昵称 |
 LikableP |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
3.618 s |
| 提交时间 |
2025-06-30 11:25:44 |
内存使用 |
7.59 MiB |
显示代码纯文本
#include <cstdio>
#include <map>
#include <queue>
#include <utility>
// #define DEBUG
template <typename T> T read();
template <typename T> void write(T, char);
template <typename T> T abs(T);
inline int ptn(int, int);
inline ::std::pair<int, int> ntp(int);
void read(char *);
void AddEdge(int, int, int);
void GoSingle(int, int, int);
void GoStraight(int, int, int);
void GoEach(int, int, int);
int cango(int, int, int);
template <typename... T> void Print(const char *Format, T... y);
const int MAXN = 1e5 + 10;
const int MAXNM = 2e5 + 10;
struct EDGE {
int v, w, next;
} edge[MAXNM << 1];
int head[MAXNM], edgeNum;
int n, m, q;
char str[MAXN];
int _map[MAXNM];
::std::map<int, bool> vis;
void work() {
n = read<int>(), m = read<int>(), q = read<int>();
for (int i = 1; i <= n; ++i) {
read(str + 1);
for (int j = 1; j <= m - 1; ++j) {
AddEdge(ptn(i, j), ptn(i, j + 1), str[j] ^ 48);
AddEdge(ptn(i, j + 1), ptn(i, j), str[j] ^ 48);
}
}
for (int i = 1; i <= n - 1; ++i) {
read(str + 1);
for (int j = 1; j <= m; ++j) {
AddEdge(ptn(i, j), ptn(i + 1, j), str[j] ^ 48);
AddEdge(ptn(i + 1, j), ptn(i, j), str[j] ^ 48);
}
}
while (q--) { // q 次询问
vis.clear();
int color = read<int>(), level = read<int>(), x = read<int>(), y = read<int>();
if (!color) level = -level; // 黑子为负，白子为正
vis[ptn(x, y)] = 1; // 先给起点标记上
GoEach(level, x, y); // 尝试走互通道路，注意互通道路必须第一个尝试
GoSingle(level, x, y); // 尝试走普通道路
GoStraight(level, x, y); // 尝试走直行道路
_map[ptn(x, y)] = level; // 加点
vis.erase(ptn(x, y)); // 起点不能算上
Print("Reached: ");
for (auto p : vis) {
Print("%d ", p.first);
}
Print("\n");
write(vis.size(), '\n');
} // q 次询问
}
int T;
int main() {
#ifndef DEBUG
freopen("chess.in", "r", stdin);
freopen("chess.out", "w", stdout);
#endif
T = read<int>();
while (T--) {
work();
}
return 0;
}
int cango(int level, int x, int y) { // 判断 level 等级的点是否能走到点 (x, y)
if (!(x >= 1 && x <= n && y >= 1 && y <= n)) return 0; // 越界返回 0
int grid = _map[ptn(x, y)];
if (!grid) return 1; // 目标点没东西，能走，返回 1
if ((grid < 0 && level < 0) || (grid > 0 && level > 0) || (abs(grid) > abs(level)))
return 0; // 颜色相同或等级比目标点低，不能走，返回 0
return 2; // 能吃目标点，返回 2
}
void GoSingle(int level, int x, int y) {
Print("Start going single\n");
for (int i = head[ptn(x, y)]; i; i = edge[i].next) { // 遍历四个方向
int v = edge[i].v, w = edge[i].w;
if (w == 1) { // 是普通道路
if (cango(level, ntp(v).first, ntp(v).second)) { // 能走
vis[v] = 1; // 就走
Print("set vis[%d] to 1\n", v);
}
}
}
}
void GoEach(int level, int x, int y) {
Print("Start going each\n");
::std::queue<int> q;
q.push(ptn(x, y)); // 添加起点
while (!q.empty()) { // 重复直到队列为空
int npos = q.front(); // 取出队首
Print("(%d)(%d %d)\n", npos, ntp(npos).first, ntp(npos).second);
q.pop(); // 弹出队首
for (int i = head[npos]; i; i = edge[i].next) { // 遍历和队首相连的边
int v = edge[i].v, w = edge[i].w;
Print("Checking edge (v:%d,w:%d)\n", v, w);
if (w != 3 || vis[v]) continue; // 不是互通道路或者目标点走过了就跳过
Print("Pass check\n");
int go = cango(level, ntp(v).first, ntp(v).second); // 计算是否能到达
if (go == 1) { // 可正常到达
vis[v] = 1; // 标记
Print("Set vis[%d] to 1 with push\n", v);
q.push(v); // 加入队列
} else if (go == 2) { // 有点但是可以吃
vis[v] = 1; // 标记，不加入队列
Print("Set vis[%d] to 1 without push\n", v);
}
}
}
}
void GoStraight(int level, int x, int y) {
Print("Start going straight\n");
for (int i = head[ptn(x, y)]; i; i = edge[i].next) { // 遍历和起点相连的边
int v = edge[i].v, w = edge[i].w;
if (w != 2) continue; // 不是直行道路就跳过
int nx = x, ny = y; // 否则就开始走
int dx = ntp(v).first - nx, dy = ntp(v).second - ny; // 计算偏移
while (true) { // 重复走
int cx = nx + dx, cy = ny + dy; // 计算目标点
int go = cango(level, cx, cy);
if (go == 0) break; // 不能走
else if (go == 1) vis[ptn(cx, cy)] = 1, Print("Set vis[%d] to 1\n", ptn(cx, cy)); // 能走
else if (go == 2) { // 能吃子
vis[ptn(cx, cy)] = 1;
Print("Set vis[%d] to 1\n", ptn(cx, cy));
break; // 吃完子之后不能再走
}
nx = cx; // 设置新的坐标
ny = cy; // 设置新的坐标
Print("(%d, %d)\n", nx, ny);
}
}
}
inline int ptn(int x, int y) {
return (x - 1) * n + y;
}
inline ::std::pair<int, int> ntp(int num) {
return ::std::make_pair((num - 1) / m + 1, (num - 1) % m + 1);
}
void AddEdge(int u, int v, int w) {
edge[++edgeNum] = {v, w, head[u]};
head[u] = edgeNum;
}
template <typename T> T abs(T x) {
return x > 0 ? x : -x;
}
template <typename... T> void Print(const char *Format, T... y) {
#ifdef DEBUG
printf(Format, y...);
#endif
}
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
template <typename T> T read() {
T res = 0, f = 1;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
f = -1;
for (; isdigit(ch); ch = getchar())
res = (res << 3) + (res << 1) + (ch ^ 48);
return res * f;
}
#define isspace(ch) (ch == '\n' || ch == ' ')
void read(char *str) {
char ch = getchar();
for (; isspace(ch); ch = getchar());
for (; !isspace(ch); ch = getchar())
*str++ = ch;
*str = 0;
}
template <typename T> void write(T x, char ed) {
if (x < 0)
x = -x, putchar('-');
static int sta[sizeof(T) << 2], top = 0;
do {
sta[++top] = x % 10;
x /= 10;
} while (x);
while (top) {
putchar(sta[top--] ^ 48);
}
putchar(ed);
}