P9898 『PG2』猪棋 题解
首先我们第一步一定是要下最中间的。
我：
(500,500)
(501,501)地图（X 为我，O 为 AI，. 为空地）：
X.
.XAI 此时有三种选择：
- 两个
.都不堵。
如此时：
……
AI：
(499,500)
(499,501)那么我们便可以下成：
……
我：
(500,501)
(501,500)赢得棋局。
- 只堵其中一个
.。
这里先给一个结论，当我们有一个形如：
???
.X.
.XX
?..方向无所谓，我们就可以在一步之内取得胜利。
也很好证，证明过程如下：
如果：
- 此时是我们的回合。
直接赢了没啥说的。
- 此时是 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;
}
}
}
}
}