题解：P9898 『PG2』猪棋

· · 题解

这里给出一个 4 步以内结束对局的做法。

sol

首先我们分析一下什么状态对局可以在 1 步之内结束。因为我们只有 2 步，所以当有 3 种及以上的赢法的时候必胜。那么就会有两类：

:::info[第一类盘面]

.o.
.oo
...

无论放哪里都不可能堵完。

:::

:::info[第二类盘面]

..    ..
oo    oo    .o
..    xx    o.
1     2     3

堵死第一种需要 2 棋子，第二和第三种需要 1 棋子。第一种可以迫使对方被动防守。

:::

接下来考虑对局过程中，后手一定是遵循对自己有利的原则。

具体地，如果后手下之前场上出现了先手有可能赢的盘面，后手一定会堵。同时如果后手堵的所有情况中存在一种可以让后手出现可能赢的盘面的情况，那么后手一定会选择这些情况。

同时对局过程中不可以让后手控场。

具体地，如果后手出现上述第二类盘面中的第一种情况，那么先手就不得不耗费 2 枚棋子解决这类情况，这样后手可以一直进攻，达成控场，这样绝对无法在 100 步内结束不了战局。

注意，如果某个时刻后手有可能赢不代表后手可以控场，后手可能赢我们可以只用 1 枚棋子堵，另外 1 枚仍然作为进攻使用。

这是很重要的，对对局策略有一定的启发性。

接下来讲对局策略。在棋盘中心即 (500,500),(501,501) 落子。

o.
.o

先看后手主动进攻的情况。

..x    ...
ox.    oxx
.o.    .o.
 1      2

只有这两种可以对先手造成威胁。如果别的情况可以通过水平翻转、上下翻转或者轴对称变为这两种的视为相同的。

:::success[情况1]

此时我们先堵 1 枚，然后在左侧冲。

...x
ooxo
..o.

后手被迫堵住左边的 o 连通块。

12.x
ooxo
34o.

如果堵的位置是 1,3 或者 2,3 可以直接在最下面的 o 下方横放两个。

12.x
ooxo
3.o.
..oo

如果堵的位置是 2,4 可以在最左侧 o 的左边纵向放两个。

o.2.x
oooxo
..4o.

如果堵的位置是 1,4 可以在右下角放 1 个构成 2 个可能赢的位置，同时在最左侧再放一个，就构成 3 个可能赢的地方。

.1..x.
oooxo.
..4oo.
......
该情况必胜。

:::success[情况2]

...
oxx
.o.

消除威胁必须在右上角堵 1 个，然后我们直接在左边冲。

...o
ooxx
..o.

这时候后手被迫堵左边的两个 o 构成的赢的方案。这时候我们直接在右上角的 o 上方补一个，最下面的 o 下方补一个就一定能保证出现 3 个可能赢的位置。

...o
34.o
ooxx
12o.
..o.
该情况必胜。

对于后手不进行主动进攻的有这些盘面。

x.    o.    ox.    xo.    ox
ox    xo    .ox    .xo    xo
.o    .x

还有其中一个 x 不知道飞到棋盘哪里去的也算在内。

拿个例子说明策略。

:::success[不主动进攻]

ox
xo

往右下延伸两个格。

ox..
xo2.
.1o4
..3o

这时候必须从 1,2 选一个堵，从 3,4 选一个堵。

但是无论选 3 还是 4 我们都可以在右下角的 o 下方或者右侧排两个连续的 o 让其构成第一类必胜盘面。

ox...
xo...
.xo..
..xoo
....o

上面就是个例子。

对于其他情况，如果右下无法延伸，直接向左上延伸，一定有一个方向可以。

这样我们就在步数 4 步以内把交互库干趴下了。

:::success[AC code & submission]

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
typedef long long ll;
pii a,b;
inline void get(){cin>>a.x>>a.y>>b.x>>b.y;}
inline void add(int ax,int ay,int bx,int by){
    cout<<ax<<" "<<ay<<" "<<bx<<" "<<by<<"\n";
    cout.flush();
    get();
}
inline void done(int ax,int ay,int bx,int by){
    cout<<ax<<" "<<ay<<" "<<bx<<" "<<by<<"\n";
    cout.flush();
    exit(0);
}
inline bool in(vector<pii>ck){
    bool f1(false),f2(true);
    for(auto i:ck){
        if(i==a) f1=true;
        if(i==b) f2=true;
    }return f1&f2;
}
inline bool check(int ax,int ay,int bx,int by){
    pii c({ax,ay}),d({bx,by});
    return (c==a && d==b) || (c==b && d==a);
}
inline bool neq(int ax,int ay){
    pii c({ax,ay});
    return (c!=a) && (c!=b);
}
int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0); 
    add(500,500,501,501);
    if(neq(500,501) && neq(501,500)) done(500,501,501,500);
    if(check(500,501,501,500) || check(499,500,500,501) || check(500,499,501,500)){
        add(502,502,503,503);
        if(neq(502,501) && neq(501,502)) done(501,502,502,501);
        if(neq(503,502) && neq(502,503)) done(502,503,503,502);
        if(neq(502,503)){
            add(503,504,504,504);
            if(neq(504,503)) done(504,503,201,20);
            if(neq(502,503) && neq(502,504)) done(502,503,502,504);
            if(neq(503,505) && neq(504,505)) done(503,505,504,505);
        }
        if(neq(503,502)){
            add(504,503,504,504);
            if(neq(503,504)) done(503,504,201,20);
            if(neq(503,502) && neq(504,502)) done(503,502,504,502);
            if(neq(505,503) && neq(505,504)) done(505,503,505,504);
        }
    }
    if(check(500,501,501,502) || check(501,500,502,501)){
        add(499,499,498,498);
        if(neq(499,500) && neq(500,499)) done(499,500,500,499);
        if(neq(498,499) && neq(499,498)) done(498,499,499,498);
        if(neq(499,498)){
            add(498,497,499,497);
            if(neq(499,498)) done(499,498,201,20);
            if(neq(497,497) && neq(497,498)) done(497,497,497,498);
            if(neq(498,496) && neq(499,496)) done(498,496,499,496);
        }
        if(neq(498,499)){
            add(497,498,497,499);
            if(neq(498,499)) done(498,499,201,20);
            if(neq(496,498) && neq(496,499)) done(496,498,496,499);
            if(neq(497,497) && neq(498,497)) done(497,497,498,497);
        }
    }
    if(check(500,501,499,502)){
        add(500,499,500,502);
        if(neq(499,499) && neq(499,500)) done(499,499,499,500);
        if(neq(501,499) && neq(501,500)) done(501,499,501,500);
        if(check(499,500,501,500)){
            add(500,498,500,503);
            if(neq(499,498) && neq(499,499)) done(499,498,499,499);
            if(neq(501,498) && neq(501,499)) done(501,498,501,499);
            if(neq(501,502) && neq(501,503)) done(501,502,501,503);
        }
        if(check(499,499,501,499) || check(499,500,501,499)){
            add(502,501,502,502);
            if(neq(501,502)) done(501,502,201,20);
            if(neq(501,500) && neq(502,500)) done(501,500,502,500);
            if(neq(503,501) && neq(503,502)) done(503,501,503,502);
        }
        if(check(499,499,501,500)){
            add(500,498,501,502);
            if(neq(501,498) && neq(501,499)) done(501,498,501,499);
            if(neq(502,501) && neq(502,502)) done(502,501,502,502);
            if(neq(500,503) && neq(501,503)) done(500,503,501,503);
        }
    }
    if(check(501,500,502,499)){
        add(501,499,501,502);
        if(neq(502,501) && neq(502,502)) done(502,501,502,502);
        if(neq(500,501) && neq(500,502)) done(500,501,500,502);
        if(check(500,502,502,502) || check(500,502,502,501)){
            add(499,499,499,500);
            if(neq(500,499)) done(500,499,201,20);
            if(neq(498,499) && neq(498,500)) done(498,499,498,500);
            if(neq(499,501) && neq(500,501)) done(499,501,500,501); 
        }
        if(check(500,501,502,501)){
            add(501,503,500,503);
            if(neq(500,502)) done(500,502,201,20);
            if(neq(502,502) && neq(502,503)) done(500,502,502,503);
            if(neq(500,504) && neq(501,504)) done(500,504,501,504);
        }
        if(check(500,501,502,502)){
            add(500,499,501,503);
            if(neq(500,498) && neq(501,498)) done(500,498,501,498);
            if(neq(499,499) && neq(499,500)) done(499,499,499,500);
            if(neq(500,502) && neq(500,503)) done(500,502,500,503);
        }
    }
    if(check(500,501,500,502)){
        add(499,502,500,499);
        if(neq(499,499) && neq(499,500)) done(499,499,499,500);
        if(neq(501,499) && neq(501,500)) done(501,499,501,500);
        if(check(501,499,499,499) || check(501,499,499,500)){
            add(502,501,502,502);
            if(neq(501,502)) done(501,502,201,20);
            if(neq(501,500) && neq(502,500)) done(501,500,502,500);
            if(neq(503,501) && neq(503,502)) done(503,501,503,502);
        }
        if(check(499,500,501,500)){
            add(499,498,500,498);
            if(neq(499,499)) done(499,499,201,20);
            if(neq(499,497) && neq(500,497)) done(499,497,500,497);
            if(neq(501,498) && neq(501,499)) done(501,498,501,499);
        }
        if(check(499,499,501,500)){
            add(500,498,498,502);
            if(neq(501,498) && neq(501,499)) done(501,498,501,499);
            if(neq(498,501) && neq(499,501)) done(498,501,499,501);
            if(neq(498,503) && neq(499,503)) done(498,503,499,503);
        }
    }
    if(check(499,501,500,501)){
        add(499,502,502,501);
        if(neq(501,500) && neq(502,500)) done(501,500,502,500);
        if(neq(501,502) && neq(502,502)) done(501,502,502,502);
        if(check(502,500,502,502) || check(502,500,501,502)){
            add(500,499,499,499);
            if(neq(499,500)) done(499,500,201,20);
            if(neq(499,498) && neq(500,498)) done(499,498,500,498);
            if(neq(501,499) && neq(501,500)) done(501,499,501,500);
        }
        if(check(501,500,501,502)){
            add(503,501,503,502);
            if(neq(502,502)) done(502,502,201,20);
            if(neq(504,501) && neq(504,502)) done(504,501,504,502);
            if(neq(502,500) && neq(503,500)) done(502,500,503,500);
        }
        if(check(501,500,502,502)){
            add(503,501,499,503);
            if(neq(498,502) && neq(498,503)) done(498,502,498,503);
            if(neq(500,502) && neq(500,503)) done(500,502,500,503);
            if(neq(502,500) && neq(503,500)) done(502,500,503,500);
        }
    }
    if(check(501,499,501,500)){
        add(502,499,501,502);
        if(neq(500,501) && neq(500,502)) done(500,501,500,502);
        if(neq(502,501) && neq(502,502)) done(502,501,502,502);
        if(check(500,502,502,501) || check(500,502,502,502)){
            add(499,499,499,500);
            if(neq(500,499)) done(500,499,201,20);
            if(neq(498,499) && neq(498,500)) done(498,499,498,500);
            if(neq(499,501) && neq(500,501)) done(499,501,500,501);
        }
        if(check(500,501,502,501)){
            add(501,503,502,503);
            if(neq(502,502)) done(502,502,201,20);
            if(neq(500,502) && neq(500,503)) done(500,502,500,503);
            if(neq(501,504) && neq(502,504)) done(501,504,502,504);
        }
        if(check(500,501,502,502)){
            add(501,503,503,499);
            if(neq(502,498) && neq(503,498)) done(502,498,503,498);
            if(neq(502,500) && neq(503,500)) done(502,500,503,500);
            if(neq(500,502) && neq(500,503)) done(500,502,500,503);
        }
    }
    if(check(501,500,502,500)){
        add(502,499,499,500);
        if(neq(499,499) && neq(500,499)) done(499,499,500,499);
        if(neq(499,501) && neq(500,501)) done(499,501,500,501);
        if(check(499,499,499,501) || check(500,499,499,501)){
            add(501,502,502,502);
            if(neq(502,501)) done(502,501,201,20);
            if(neq(500,501) && neq(500,502)) done(500,501,500,502);
            if(neq(501,503) && neq(502,503)) done(501,503,502,503);
        }
        if(check(500,499,500,501)){
            add(498,499,498,500);
            if(neq(499,499)) done(499,499,201,20);
            if(neq(498,501) && neq(499,501)) done(498,501,499,501);
            if(neq(497,499) && neq(497,500)) done(497,499,497,500);
        }
        if(check(499,499,500,501)){
            add(502,498,501,502);
            if(neq(501,498) && neq(501,499)) done(501,498,501,499);
            if(neq(503,498) && neq(503,499)) done(503,498,503,499);
            if(neq(502,501) && neq(502,502)) done(502,501,502,502);
        }
    }
    if(check(500,501,500,501) && a==make_pair(500,501)) swap(a,b);
    else if(check(501,500,501,500) && a==make_pair(501,500)) swap(a,b);
    if(a.x<=500 && a.y<=500){
        add(502,502,503,503);
        if(neq(502,501) && neq(501,502)) done(501,502,502,501);
        if(neq(503,502) && neq(502,503)) done(502,503,503,502);
        if(neq(502,503)){
            add(503,504,504,504);
            if(neq(504,503)) done(504,503,201,20);
            if(neq(502,503) && neq(502,504)) done(502,503,502,504);
            if(neq(503,505) && neq(504,505)) done(503,505,504,505);
        }
        if(neq(503,502)){
            add(504,503,504,504);
            if(neq(503,504)) done(503,504,201,20);
            if(neq(503,502) && neq(504,502)) done(503,502,504,502);
            if(neq(505,503) && neq(505,504)) done(505,503,505,504);
        }
    }else if(a.x>=501 && a.y>=501){
        add(499,499,498,498);
        if(neq(499,500) && neq(500,499)) done(499,500,500,499);
        if(neq(498,499) && neq(499,498)) done(498,499,499,498);
        if(neq(499,498)){
            add(498,497,499,497);
            if(neq(499,498)) done(499,498,201,20);
            if(neq(497,497) && neq(497,498)) done(497,497,497,498);
            if(neq(498,496) && neq(499,496)) done(498,496,499,496);
        }
        if(neq(498,499)){
            add(497,498,497,499);
            if(neq(498,499)) done(498,499,201,20);
            if(neq(496,498) && neq(496,499)) done(496,498,496,499);
            if(neq(497,497) && neq(498,497)) done(497,497,498,497);
        }
    }else{
        add(502,502,503,503);
        if(neq(502,501) && neq(501,502)) done(501,502,502,501);
        if(neq(503,502) && neq(502,503)) done(502,503,503,502);
        if(neq(502,503)){
            add(503,504,504,504);
            if(neq(504,503)) done(504,503,201,20);
            if(neq(502,503) && neq(502,504)) done(502,503,502,504);
            if(neq(503,505) && neq(504,505)) done(503,505,504,505);
        }
        if(neq(503,502)){
            add(504,503,504,504);
            if(neq(503,504)) done(503,504,201,20);
            if(neq(503,502) && neq(504,502)) done(503,502,504,502);
            if(neq(505,503) && neq(505,504)) done(505,503,505,504);
        }
    }
    return 0;
}

:::