CSDN话题挑战赛第2期
参赛话题：学习笔记
学习之路，长路漫漫，写学习笔记的过程就是把知识讲给自己听的过程。这个过程中，我们去记录思考的过程，便于日后复习，梳理自己的思路。学习之乐，独乐乐，不如众乐乐，把知识讲给更多的人听，何乐而不为呢?
目录
围棋是起源于中国有悠久历史的策略性棋类游戏。它的规则如下：
1. 棋盘19*19。
2. 棋子分黑白两色，双方各执一色。
3. 下法：每次黑或白着一子于棋盘的空点上。棋子下定后，不再向其他点移动。
4. 棋子的气：一个棋子在棋盘上，与它相邻的空点是这个棋子的“气”（这里相邻是指两个点有公共边）。 相邻的点上如果有同色棋子存在，这些棋子就相互连接成一个不可分割的整体，气合并计算。
相邻的点上如果有异色棋子存在，此处的气便不存在。
如果棋子所在的连通块失去所有的气，即为无气之子，不能在棋盘上存在。
5. 提子：把无气之子清理出棋盘的手段叫“提子”。提子有二种：
1) 着子后，对方棋子无气，应立即提取对方无气之子。
2) 着子后，双方棋子都呈无气状态，应立即提取对方无气之子。
6. 禁着点：棋盘上的任何一空点，如果某方在此下子，会使该子立即呈无气状态，同时又不能提取对方的棋子，这个点叫做“禁着点”，该方不能在此下子。
7. 禁止全局同形：无论哪一方，在成功进行了着子、提子操作后，棋盘局面不能和任何之前的局面相同。
你要做的是：输入一些操作，从空棋盘开始模拟这些操作。
对于每一步，若结果不正确，则输出对应的miss并且忽略这个操作，并在最后输出棋盘的局面。
第一行，测试数据组数≤100 第二行，每组测试数据，执行的步数 n ≤ 2000 然后 n 行 B x y W x y (1 ≤ x ≤ 19,1 ≤ y ≤ 19) 其中，二元组 x,y 表示围棋棋盘上第 x 行第 y 列对应的点。 输入数据保证是黑白轮流下的。
多行 对于miss的情况，输出是哪一种错误格式，其中： miss 1 表示下的位置已经有棋了 miss 2 表示违反规则6 miss 3 表示违反规则7 对于正常的操作，不用输出。 最后输出最终盘面。“B表示黑子，W表示白子，如果是空点的话，就输出'.'字符。”
- 1
- 12
- B 1 3
- W 1 2
- B 2 4
- W 2 1
- B 1 1
- W 2 3
- B 3 3
- W 3 2
- B 1 1
- W 2 3
- B 2 2
- W 2 3
- miss 2
- miss 2
- miss 1
- miss 3
- .WB................
- WB.B...............
- .WB................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
- ...................
一道模拟题。
模拟题重在如何实现，接下来挑出几个难以实现的地方说一说：
对于一块棋，有「气」就能活，没有「气」就会死。下面的 bool live(int, int, char) 处理了这个过程：
. 就代表找到了至少一口气，就是暂时活棋。考虑到围棋还有一个落子问题，也就是说不一定是落子之后自己没有「气」就会死，而是对方有「气」并且自己没有才会死。
这里采用的判断方法也很巧妙：
如果自己可以“提”走别人，自己一定不会死（给我留出了「气」），如果自己提不走别人，别人堵住了我所有的「气」，我就会死。
对于不能发生相同局面，这里可以考虑与 2. 难点建立联系，建立两个数组，一个是试错数组 now，另一个用于保存我之前的答案 old。
如果这里的数组 now 经过哈希之后有重复，就让 now ←\leftarrow← old，如果上述判断都没有问题，就让 old ←\leftarrow← now。
判断局面是否相同，直接哈希并把它扔到 set 里面判重一下就好了，这里采用的是双哈希，碰撞概率非常低。
- #include
- #include
- #include
- int init(){
- char c = getchar();
- int x = 0, f = 1;
- for (; c < '0' || c > '9'; c = getchar())
- if (c == '-') f = -1;
- for (; c >= '0' && c <= '9'; c = getchar())
- x = (x << 1) + (x << 3) + (c ^ 48);
- return x * f;
- }
- void print(int x){
- if (x < 0) x = -x, putchar('-');
- if (x > 9) print(x / 10);
- putchar(x % 10 + '0');
- }
- const int N = (int) 2e1, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
- const int Buff1 = 131, Buff2 = 171, Mod1 = 998244353, Mod2 = (int) 1e9 + 7;
- char now[N][N], old[N][N];
- void work(bool tp){
- for (int i = 1; i < N; ++i)
- for (int j = 1; j < N; ++j)
- if (tp) old[i][j] = now[i][j];
- else now[i][j] = old[i][j];
- }
- int go(char ch){
- if (ch == 'W') return 0;
- if (ch == 'B') return 1;
- return 2;
- }
- std::pair<int, int> Hash(){
- int s1 = 0, s2 = 0;
- for (int i = 1; i < N; ++i)
- for (int j = 1; j < N; ++j)
- s1 = (s1 * 1ll * Buff1 + go(now[i][j])) % Mod1,
- s2 = (s2 * 1ll * Buff2 + go(now[i][j])) % Mod2;
- return std::make_pair(s1, s2);
- }
- std::set
int, int> >set; - bool vis[N][N];
- bool live(int x, int y, char ch){
- if (now[x][y] == '.') return 1;
- if (now[x][y] != ch) return 0;
- bool ans = 0; vis[x][y] = 1;
- for (int k = 0; k < 4; ++k) {
- int nx = x + dx[k], ny = y + dy[k];
- if (nx < 1 || nx >= N || ny < 1 || ny >= N) continue;
- if (!vis[nx][ny]) ans |= live(nx, ny, ch);
- }
- return ans;
- }
- void clean(int x, int y, char ch){
- now[x][y] = '.';
- for (int k = 0; k < 4; ++k) {
- int nx = x + dx[k], ny = y + dy[k];
- if (nx < 1 || nx >= N || ny < 1 || ny >= N) continue;
- if (now[nx][ny] == ch) clean(nx, ny, ch);
- }
- }
- int chk(char ch, int x, int y){
- if (now[x][y] != '.') return 1;
- now[x][y] = ch; vis[x][y] = 1;
- bool ans = live(x, y, ch);
- for (int k = 0; k < 4; ++k) {
- int nx = x + dx[k], ny = y + dy[k];
- if (!vis[nx][ny] && now[nx][ny] == 'W' + 'B' - ch && !live(nx, ny, 'W' + 'B' - ch))
- ans |= 1, clean(nx, ny, 'W' + 'B' - ch);
- }
- if (!ans) return 2;
- if (set.count(Hash())) return 3;
- return 0;
- }
- void Print(const char*str){
- for (int i = 0; str[i]; ++i)
- putchar(str[i]);
- }
- int main(){
- int T = init();
- while (T--) {
- set.clear();
- for (int i = 1; i < N; ++i)
- for (int j = 1; j < N; ++j)
- now[i][j] = old[i][j] = '.';
- int n = init();
- for (int i = 1; i <= n; ++i) {
- memset(vis, 0, sizeof(vis));
- char ch = 0;
- while (ch != 'B' && ch != 'W')
- ch = getchar();
- int x = init(), y = init();
- int tp = chk(ch, x, y);
- if (tp) Print("miss "), print(tp), putchar('\n');
- else set.insert(Hash());
- work(!tp);
- }
- for (int i = 1; i < N; ++i, putchar('\n'))
- for (int j = 1; j < N; ++j)
- putchar(now[i][j]);
- }
- }