15011418730 LV 7 @ 2025-8-24 22:52:50

自动搬运

来自洛谷，原作者为

	ivyjiao 复活了

搬运于2025-08-24 22:52:50，当前版本为作者最后更新于2023-12-14 16:35:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先我们第一步一定是要下最中间的。

我：
(500,500)
(501,501)

地图（X 为我，O 为 AI，. 为空地）：

X.
.X

AI 此时有三种选择：

两个 . 都不堵。

如此时：

……
AI：
(499,500)
(499,501)

那么我们便可以下成：

……
我：
(500,501)
(501,500)

赢得棋局。

只堵其中一个 .。

这里先给一个结论，当我们有一个形如：

???
.X.
.XX
?..

方向无所谓，我们就可以在一步之内取得胜利。

也很好证，证明过程如下：

如果：

此时是我们的回合。

直接赢了没啥说的。

此时是 AI 的回合。

我们有左、下、右上三个能凑成 $2\times 2$ 的地方，AI 只能堵两个，轮到我的回合还是赢。

说完这个结论，我们来想一下只堵一个的情况。

实际上这也是最难的情况。

容易发现 AI 堵左下还是右上是无所谓的，所以我们关注另一颗棋子的动向：

随便下。

如此时：

……
AI：
(499,499)
(500,501)

那么我们就可以：

……
我：
(502,501)
(502,502)

此时的地图：

O...
.XO.
..X.
..XX

已经构造出了我们想要的东西，赢。

与第一颗棋子相连（八连通）。

如此时：

……
AI：
(500,501)
(500,502)

那么我们可以：

……
我：
(499,501)
(501,500)

此时地图如下：

.X.
XOO
XX.

若此时 AI 把左面和下面都堵上了，我们就去上面构造那个东西，如下：

……
AI：
(501,499)
(502,500)
我：
(498,501)
(498,502)

此时地图如下：

..XX
..X.
.XOO
OXX.
.O..

已经构造出了我们想要的东西，赢。

如果 AI 没把左面和下面都堵上，直接在左面或下面一步获得胜利。

如：

……
AI：
(498,501)
(502,501)
我：
(500,499)
(501,499)

赢。

四联通还有三种方案，拓展到八连通只多了两种有效方案，都可以用类似的方法破解。

两个 . 都堵。

此时 AI 只有一种方案，我们只要继续往右下角放就行。

……
AI：
(500,501)
(501,500)
我：
(502,502)
(503.503)

接下来 AI 这步下完，我们的四个棋子如果中间两个没被堵就拿中间两个赢，下面两个没被堵就拿下面两个赢。

如果都被堵了去构造那个东西就行。

如：

……
AI：
(501,502)
(503,502)
我：
(503,504)
(504,504)

此时地图如下：

XO...
OXO..
..X..
..OXX
....X

已经构造出了我们想要的东西，赢。

其余方法同。

本题证毕。

代码如下：

#include<iostream>
using namespace std;
int x,y,xx,yy,vis[1001][1001];
int main(){
    cout<<500<<" "<<500<<endl;
    cout<<501<<" "<<501<<endl;
    vis[500][500]=1;
    vis[501][501]=1;
    cin>>x>>y>>xx>>yy;
    vis[x][y]=1;
    vis[xx][yy]=1;
    if(vis[500][501]&&vis[501][500]){
        cout<<502<<" "<<502<<endl;
        cout<<503<<" "<<503<<endl;
        cin>>x>>y>>xx>>yy;
        vis[x][y]=1;
        vis[xx][yy]=1;
        if(!vis[501][502]&&!vis[502][501]){
            cout<<501<<" "<<502<<endl;
            cout<<502<<" "<<501<<endl;
            return 0;
        }
        else if(!vis[502][503]&&!vis[503][502]){
            cout<<502<<" "<<503<<endl;
            cout<<503<<" "<<502<<endl;
            return 0;
        }
        else if(vis[503][502]){
            cout<<503<<" "<<504<<endl;
            cout<<504<<" "<<504<<endl;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(!vis[504][503]){
                cout<<504<<" "<<503<<endl;
                cout<<114<<" "<<514<<endl;
                return 0;
            }
            else if(!vis[502][503]&&!vis[502][504]){
                cout<<502<<" "<<503<<endl;
                cout<<502<<" "<<504<<endl;
                return 0;
            }
            else{
                cout<<503<<" "<<505<<endl;
                cout<<504<<" "<<505<<endl;
                return 0;
            }
        }
        else{
            cout<<504<<" "<<503<<endl;
            cout<<504<<" "<<504<<endl;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(!vis[503][504]){
                cout<<503<<" "<<504<<endl;
                cout<<114<<" "<<514<<endl;
                return 0;
            }
            else if(!vis[503][502]&&!vis[504][502]){
                cout<<503<<" "<<502<<endl;
                cout<<504<<" "<<502<<endl;
                return 0;
            }
            else{
                cout<<505<<" "<<503<<endl;
                cout<<505<<" "<<504<<endl;
                return 0;
            }
        }
    }
    else{
        if(!vis[500][501]&&!vis[501][500]){
            cout<<500<<" "<<501<<endl;
            cout<<501<<" "<<500<<endl;
            return 0;
        }
        else if(vis[500][501]&&vis[501][502]){
            cout<<499<<" "<<501<<endl;
            cout<<501<<" "<<500<<endl;
            vis[499][501]=1;
            vis[501][500]=1;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(!vis[498][501]&&!vis[498][502]&&!vis[499][500]&&!vis[498][500]&&!vis[497][501]&&!vis[497][502]){
                cout<<498<<" "<<501<<endl;
                cout<<498<<" "<<502<<endl;
                vis[498][501]=1;
                vis[498][502]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[499][502]){
                    cout<<499<<" "<<502<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[499][500]&&!vis[498][500]){
                    cout<<499<<" "<<500<<endl;
                    cout<<498<<" "<<500<<endl;
                    return 0;
                }
                else{
                    cout<<497<<" "<<501<<endl;
                    cout<<497<<" "<<502<<endl;
                    return 0;
                }
            }
            else if(!vis[500][499]&&!vis[501][499]){
                cout<<500<<" "<<499<<endl;
                cout<<501<<" "<<499<<endl;
                return 0;
            }
            else{
                cout<<502<<" "<<499<<endl;
                cout<<502<<" "<<500<<endl;
                return 0;
            }
        }
        else if(vis[500][501]&&vis[499][501]){
            cout<<501<<" "<<499<<endl;
            cout<<500<<" "<<502<<endl;
            vis[501][499]=1;
            vis[500][502]=1;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(!vis[499][503]&&!vis[500][503]&&!vis[499][504]&&!vis[500][504]&&!vis[501][502]&&!vis[501][503]&&!vis[499][502]){
                cout<<499<<" "<<503<<endl;
                cout<<500<<" "<<503<<endl;
                vis[499][503]=1;
                vis[500][503]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[499][502]){
                    cout<<499<<" "<<502<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[499][504]&&!vis[500][504]){
                    cout<<499<<" "<<504<<endl;
                    cout<<500<<" "<<504<<endl;
                    return 0;
                }
                else{
                    cout<<501<<" "<<502<<endl;
                    cout<<501<<" "<<503<<endl;
                    return 0;
                }
            }
            else if(!vis[500][499]&&!vis[501][499]){
                cout<<500<<" "<<499<<endl;
                cout<<501<<" "<<499<<endl;
                return 0;
            }
            else{
                cout<<502<<" "<<500<<endl;
                cout<<502<<" "<<501<<endl;
                return 0;
            }
        }
        else if(vis[501][500]&&vis[501][499]){
            cout<<500<<" "<<501<<endl;
            cout<<502<<" "<<500<<endl;
            vis[500][501]=1;
            vis[502][500]=1;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(!vis[503][500]&&!vis[503][501]&&!vis[502][499]&&!vis[503][499]&&!vis[504][500]&&!vis[504][501]&&!vis[502][501]){
                cout<<503<<" "<<500<<endl;
                cout<<503<<" "<<501<<endl;
                vis[503][500]=1;
                vis[503][501]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[502][501]){
                    cout<<502<<" "<<501<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[502][499]&&!vis[503][499]){
                    cout<<502<<" "<<499<<endl;
                    cout<<503<<" "<<499<<endl;
                    return 0;
                }
                else{
                    cout<<504<<" "<<500<<endl;
                    cout<<504<<" "<<501<<endl;
                    return 0;
                }
            }
            else if(!vis[500][502]&&!vis[501][502]){
                cout<<500<<" "<<502<<endl;
                cout<<501<<" "<<502<<endl;
                return 0;
            }
            else{
                cout<<499<<" "<<500<<endl;
                cout<<499<<" "<<501<<endl;
                return 0;
            }
        }
        else if(vis[501][500]&&vis[502][500]){
            cout<<500<<" "<<501<<endl;
            cout<<501<<" "<<499<<endl;
            vis[500][501]=1;
            vis[501][499]=1;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(!vis[501][498]&&!vis[502][498]&&!vis[501][497]&&!vis[502][497]&&!vis[500][499]&&!vis[500][498]&&!vis[502][499]){
                cout<<501<<" "<<498<<endl;
                cout<<502<<" "<<498<<endl;
                vis[501][498]=1;
                vis[502][498]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[502][499]){
                    cout<<502<<" "<<499<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[501][497]&&!vis[502][497]){
                    cout<<501<<" "<<497<<endl;
                    cout<<502<<" "<<497<<endl;
                    return 0;
                }
                else{
                    cout<<500<<" "<<499<<endl;
                    cout<<500<<" "<<498<<endl;
                    return 0;
                }
            }
            else if(!vis[500][502]&&!vis[501][502]){
                cout<<500<<" "<<502<<endl;
                cout<<501<<" "<<502<<endl;
                return 0;
            }
            else{
                cout<<499<<" "<<500<<endl;
                cout<<499<<" "<<501<<endl;
                return 0;
            }
        }
        else if(vis[500][501]&&vis[499][502]){
            cout<<500<<" "<<502<<endl;
            cout<<501<<" "<<502<<endl;
            vis[500][502]=1;
            vis[501][502]=1;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(!vis[500][499]&&!vis[499][499]&&!vis[501][500]&&!vis[501][499]&&!vis[500][498]&&!vis[499][498]&&!vis[499][500]){
                cout<<500<<" "<<499<<endl;
                cout<<499<<" "<<499<<endl;
                vis[500][499]=1;
                vis[499][499]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[499][500]){
                    cout<<499<<" "<<500<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[501][500]&&!vis[501][499]){
                    cout<<501<<" "<<500<<endl;
                    cout<<502<<" "<<499<<endl;
                    return 0;
                }
                else{
                    cout<<500<<" "<<498<<endl;
                    cout<<499<<" "<<498<<endl;
                    return 0;
                }
            }
            else if(!vis[502][502]&&!vis[502][503]){
                cout<<502<<" "<<502<<endl;
                cout<<502<<" "<<503<<endl;
                return 0;
            }
            else{
                cout<<500<<" "<<503<<endl;
                cout<<501<<" "<<503<<endl;
                return 0;
            }
        }
        else if(vis[501][500]&&vis[502][499]){
            cout<<500<<" "<<499<<endl;
            cout<<501<<" "<<499<<endl;
            vis[500][499]=1;
            vis[501][499]=1;
            cin>>x>>y>>xx>>yy;
            vis[x][y]=1;
            vis[xx][yy]=1;
            if(!vis[500][502]&&!vis[501][502]&&!vis[500][503]&&!vis[501][503]&&!vis[502][501]&&!vis[502][502]&&!vis[500][501]){
                cout<<500<<" "<<502<<endl;
                cout<<501<<" "<<502<<endl;
                vis[500][502]=1;
                vis[501][502]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[500][501]){
                    cout<<500<<" "<<501<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[502][501]&&!vis[502][502]){
                    cout<<502<<" "<<501<<endl;
                    cout<<502<<" "<<502<<endl;
                    return 0;
                }
                else{
                    cout<<500<<" "<<503<<endl;
                    cout<<501<<" "<<503<<endl;
                    return 0;
                }
            }
            else if(!vis[500][498]&&!vis[501][498]){
                cout<<500<<" "<<498<<endl;
                cout<<501<<" "<<498<<endl;
                return 0;
            }
            else{
                cout<<499<<" "<<499<<endl;
                cout<<499<<" "<<500<<endl;
                return 0;
            }
        }
        else if(vis[501][500]){
            if(!vis[500][502]&&!vis[501][502]&&!vis[500][503]&&!vis[501][503]&&!vis[502][501]&&!vis[502][502]&&!vis[500][501]){
                cout<<500<<" "<<502<<endl;
                cout<<501<<" "<<502<<endl;
                vis[500][502]=1;
                vis[501][502]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[500][501]){
                    cout<<500<<" "<<501<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[500][503]&&!vis[501][503]){
                    cout<<500<<" "<<503<<endl;
                    cout<<501<<" "<<503<<endl;
                    return 0;
                }
                else{
                    cout<<502<<" "<<501<<endl;
                    cout<<502<<" "<<502<<endl;
                    return 0;
                }
            }
            else{
                cout<<499<<" "<<500<<endl;
                cout<<499<<" "<<501<<endl;
                vis[499][500]=1;
                vis[499][501]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[500][501]){
                    cout<<500<<" "<<501<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[500][499]&&!vis[499][499]){
                    cout<<500<<" "<<499<<endl;
                    cout<<499<<" "<<499<<endl;
                    return 0;
                }
                else{
                    cout<<498<<" "<<500<<endl;
                    cout<<498<<" "<<501<<endl;
                    return 0;
                }
            }
        }
        else{
            if(!vis[502][500]&&!vis[502][501]&&!vis[503][500]&&!vis[503][501]&&!vis[501][502]&&!vis[502][502]&&vis[501][500]){
                cout<<502<<" "<<500<<endl;
                cout<<502<<" "<<501<<endl;
                vis[502][500]=1;
                vis[502][501]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[501][500]){
                    cout<<501<<" "<<500<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[503][500]&&!vis[503][501]){
                    cout<<503<<" "<<500<<endl;
                    cout<<503<<" "<<501<<endl;
                    return 0;
                }
                else{
                    cout<<501<<" "<<502<<endl;
                    cout<<502<<" "<<502<<endl;
                    return 0;
                }
            }
            else{
                cout<<500<<" "<<499<<endl;
                cout<<501<<" "<<499<<endl;
                vis[500][499]=1;
                vis[501][499]=1;
                cin>>x>>y>>xx>>yy;
                vis[x][y]=1;
                vis[xx][yy]=1;
                if(!vis[501][500]){
                    cout<<501<<" "<<500<<endl;
                    cout<<114<<" "<<514<<endl;
                    return 0;
                }
                else if(!vis[499][500]&&!vis[499][499]){
                    cout<<499<<" "<<500<<endl;
                    cout<<499<<" "<<499<<endl;
                    return 0;
                }
                else{
                    cout<<500<<" "<<498<<endl;
                    cout<<501<<" "<<498<<endl;
                    return 0;
                }
            }
        }
    }
}

ID

9435

时间

5000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

『PG2』猪棋

信息

1 条题解

自动搬运

以下是正文

『PG2』猪棋

信息

还没有账户？

登录