轉(zhuǎn)載請(qǐng)注明出處：優(yōu)
YoU
http://user.qzone.qq.com/289065406/blog/1308890557
-
大致題意： -
一種類似圍棋的游戲，有黑白兩種顏色的棋子。-
規(guī)定黑棋為先手，白棋為后手。-
放下棋子 A 后，若 A 的 8 個(gè)馬步方位（即中國(guó)象棋的“馬”或國(guó)際象棋的“騎士”的“日”字走法）至少存在 1 個(gè)同色的棋子，且當(dāng)連接 A 與這些棋子時(shí)，其連線不切割已經(jīng)有的線，則連接。-
黑棋的目標(biāo)是連出一條從 X 軸的 0 列到 N 列的路；-
白棋的目標(biāo)是連出一條從 Y 軸的 0 行到 N 行的路。-
就是說(shuō)某一方要贏棋，當(dāng)且僅當(dāng)其把自己的兩個(gè)“終域”連接在一起，完全阻隔對(duì)方的連接。-
按照以上規(guī)則，判斷黑棋所走的最后一步是否為贏棋的一步。-
-
解題思路： -
比較麻煩的模擬，但是難度不大，難點(diǎn)主要在于判斷連線是否相交。-
-
如上圖放下一只棋子后，先檢查其附近的 8 個(gè)方位是否存在同色棋子，若存在，則檢查是否允許與該同色棋子連線。-
檢查連線方法如下圖，以 30 度的方位為例：-
-
如上圖，當(dāng)放下新棋子后，若檢測(cè)到 30 度方位存在與其同色的棋子，則在連接藍(lán)線之前，先檢查是否已存在 9 條紅色的線，當(dāng)且僅當(dāng)這 9 條紅線都不存在時(shí)，才允許連接藍(lán)線。-
其他 7 個(gè)方位也是同樣做法。-
-
最后要判斷黑棋的最后一步是不是為贏棋的一步，只需要做兩次 BFS 。-
第一次 BFS ：以黑棋的 0 終域?yàn)槠瘘c(diǎn)，尋找是否存在到 N 終域的路。-
第二次 BFS ：先刪去最后一步棋，再以黑棋的 0 終域?yàn)槠瘘c(diǎn)，尋找是否存在到 N 終域的路。-
當(dāng)?shù)谝淮? BFS 結(jié)果為 true ，第二次 BFS 結(jié)果為 false 時(shí)，則說(shuō)明黑棋的最后一步為贏棋的一步。 ??-
Source修正：
http://mcpc.cigas.net/archives.html
//Memory Time
//340K 0MS
#include<iostream>
using namespace std;
const int size=23;
const int num=251;
int n; //chess size
int m; //move steps
int lastx,lasty;
int map[size][size]; //對(duì)坐標(biāo)為(x,y)的棋子編號(hào)
bool link[num][num]; //標(biāo)記某兩個(gè)編號(hào)的棋子是否有連線
int posx[]={0,-1,-2,-2,-1,1,2,2,1}; //對(duì)應(yīng)于(x,y)的八個(gè)方位
int posy[]={0,2,1,-1,-2,-2,-1,1,2};
typedef class chess
{
public:
int color; //黑棋:1 白棋:0
int r,c;
int connet[8]; //記錄與當(dāng)前棋子直接相連的棋子編號(hào)
int pc; //connet的指針
chess()
{
color=-1;
pc=0;
}
}PEG;
void LinePeg(PEG* peg,int i); //把棋子peg[i]與與其相鄰的八個(gè)方位的同色棋子連線
bool CheckWin(PEG* peg,bool flag); //BFS,檢查先手(黑棋)是否把終域連接在一起(贏家)
int main(void)
{
while(cin>>n>>m)
{
if(!n && !m)
break;
memset(map,0,sizeof(map));
memset(link,false,sizeof(link));
PEG* peg=new PEG[m+1];
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
map[x][y]=i; //編號(hào)記錄
peg[i].r=x;
peg[i].c=y;
if(i%2)
peg[i].color=1; //黑棋
else
peg[i].color=0; //白棋
if(i==m) //記錄最后一步棋
{
lastx=x;
lasty=y;
}
LinePeg(peg,i); //把最新下的棋子與其附近的同色棋子相連
}
if(CheckWin(peg,true) && !CheckWin(peg,false))
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
return 0;
}
/*把棋子(x,y)與與其相鄰的八個(gè)方位的同色棋子連線*/
void LinePeg(PEG* peg,int i)
{
int color=peg[i].color;
for(int k=1;k<=8;k++)
{
int r=peg[i].r+posx[k];
int c=peg[i].c+posy[k];
if(r>=0 && r<=n && c>=0 && c<=n) //檢查邊界
{
if(map[r][c] && peg[ map[r][c] ].color==color) //檢查顏色
{
switch(k) //"日"字對(duì)角連線
{
case 1: //30度方位
{
if(link[ map[r][c-2] ][ map[r+1][c] ])
break;
if(c-3>=0 && link[ map[r][c-3] ][ map[r+1][c-1] ])
break;
if(c+1<=n && link[ map[r][c-1] ][ map[r+1][c+1] ])
break;
if(r-1>=0)
{
if(link[ map[r-1][c-2] ][ map[r+1][c-1] ])
break;
if(link[ map[r-1][c-1] ][ map[r+1][c] ])
break;
if(link[ map[r-1][c] ][ map[r+1][c-1] ])
break;
}
if(r+2<=n)
{
if(link[ map[r+2][c-2] ][ map[r][c-1] ])
break;
if(link[ map[r+2][c-1] ][ map[r][c-2] ])
break;
if(link[ map[r+2][c] ][ map[r][c-1] ])
break;
}
int a=map[peg[i].r][peg[i].c];
int b=map[r][c];
peg[a].connet[peg[a].pc++]=b;
peg[b].connet[peg[b].pc++]=a;
link[a][b]=link[b][a]=true;
break;
}
case 2: //60度方位
{
if(link[ map[r][c-1] ][ map[r+2][c] ])
break;
if(r-1>=0 && link[ map[r-1][c-1] ][ map[r+1][c] ])
break;
if(r+3<=n && link[ map[r+1][c-1] ][ map[r+3][c] ])
break;
if(c-2>=0)
{
if(link[ map[r][c-2] ][ map[r+1][c] ])
break;
if(link[ map[r+1][c-2] ][ map[r+2][c] ])
break;
if(link[ map[r+2][c-2] ][ map[r+1][c] ])
break;
}
if(c+1<=n)
{
if(link[ map[r][c-1] ][ map[r+1][c+1] ])
break;
if(link[ map[r+1][c-1] ][ map[r][c+1] ])
break;
if(link[ map[r+1][c-1] ][ map[r+2][c+1] ])
break;
}
int a=map[peg[i].r][peg[i].c];
int b=map[r][c];
peg[a].connet[peg[a].pc++]=b;
peg[b].connet[peg[b].pc++]=a;
link[a][b]=link[b][a]=true;
break;
}
case 3: //120度方位
{
if(link[ map[r][c+1] ][ map[r+2][c] ])
break;
if(r-1>=0 && link[ map[r-1][c+1] ][ map[r+1][c] ])
break;
if(r+3<=n && link[ map[r+1][c+1] ][ map[r+3][c] ])
break;
if(c-1>=0)
{
if(link[ map[r][c-1] ][ map[r+1][c+1] ])
break;
if(link[ map[r+1][c-1] ][ map[r][c+1] ])
break;
if(link[ map[r+2][c-1] ][ map[r+1][c+1] ])
break;
}
if(c+2<=n)
{
if(link[ map[r+1][c] ][ map[r][c+2] ])
break;
if(link[ map[r+2][c] ][ map[r+1][c+2] ])
break;
if(link[ map[r+1][c] ][ map[r+2][c+2] ])
break;
}
int a=map[peg[i].r][peg[i].c];
int b=map[r][c];
peg[a].connet[peg[a].pc++]=b;
peg[b].connet[peg[b].pc++]=a;
link[a][b]=link[b][a]=true;
break;
}
case 4: //150度方位
{
if(link[ map[r][c+2] ][ map[r+1][c] ])
break;
if(c-1>=0 && link[ map[r+1][c-1] ][ map[r][c+1] ])
break;
if(c+3<=n && link[ map[r+1][c+1] ][ map[r][c+3] ])
break;
if(r-1>=0)
{
if(link[ map[r-1][c] ][ map[r+1][c+1] ])
break;
if(link[ map[r-1][c+1] ][ map[r+1][c] ])
break;
if(link[ map[r-1][c+2] ][ map[r+1][c+1] ])
break;
}
if(r+2<=n)
{
if(link[ map[r][c+1] ][ map[r+2][c] ])
break;
if(link[ map[r][c+1] ][ map[r+2][c+2] ])
break;
if(link[ map[r][c+2] ][ map[r+2][c+1] ])
break;
}
int a=map[peg[i].r][peg[i].c];
int b=map[r][c];
peg[a].connet[peg[a].pc++]=b;
peg[b].connet[peg[b].pc++]=a;
link[a][b]=link[b][a]=true;
break;
}
case 5: //210度方位
{
if(link[ map[r-1][c] ][ map[r][c+2] ])
break;
if(c-1>=0 && link[ map[r-1][c-1] ][ map[r][c+1] ])
break;
if(c+3<=n && link[ map[r-1][c+1] ][ map[r][c+3] ])
break;
if(r-2>=0)
{
if(link[ map[r-2][c] ][ map[r][c+1] ])
break;
if(link[ map[r-2][c+1] ][ map[r][c+2] ])
break;
if(link[ map[r-2][c+2] ][ map[r][c+1] ])
break;
}
if(r+1<=n)
{
if(link[ map[r][c] ][ map[r-1][c+1] ])
break;
if(link[ map[r+1][c+1] ][ map[r-1][c] ])
break;
if(link[ map[r+1][c+2] ][ map[r-1][c+1] ])
break;
}
int a=map[peg[i].r][peg[i].c];
int b=map[r][c];
peg[a].connet[peg[a].pc++]=b;
peg[b].connet[peg[b].pc++]=a;
link[a][b]=link[b][a]=true;
break;
}
case 6: //240度方位
{
if(link[ map[r-2][c] ][ map[r][c+1] ])
break;
if(r-3>=0 && link[ map[r-3][c] ][ map[r-1][c+1] ])
break;
if(r+1<=n && link[ map[r-1][c] ][ map[r+1][c+1] ])
break;
if(c-1>=0)
{
if(link[ map[r-2][c-1] ][ map[r-1][c+1] ])
break;
if(link[ map[r-1][c-1] ][ map[r][c+1] ])
break;
if(link[ map[r][c-1] ][ map[r-1][c+1] ])
break;
}
if(c+2<=n)
{
if(link[ map[r-1][c] ][ map[r-2][c+2] ])
break;
if(link[ map[r-2][c] ][ map[r-1][c+2] ])
break;
if(link[ map[r-1][c] ][ map[r][c+2] ])
break;
}
int a=map[peg[i].r][peg[i].c];
int b=map[r][c];
peg[a].connet[peg[a].pc++]=b;
peg[b].connet[peg[b].pc++]=a;
link[a][b]=link[b][a]=true;
break;
}
case 7: //300度方位
{
if(link[ map[r-2][c] ][ map[r][c-1] ])
break;
if(r-3>=0 && link[ map[r-3][c] ][ map[r-1][c-1] ])
break;
if(r+1<=n && link[ map[r-1][c] ][ map[r+1][c-1] ])
break;
if(c-2>=0)
{
if(link[ map[r-2][c-2] ][ map[r-1][c] ])
break;
if(link[ map[r-1][c-2] ][ map[r-2][c] ])
break;
if(link[ map[r][c-2] ][ map[r-1][c] ])
break;
}
if(c+1<=n)
{
if(link[ map[r-1][c-1] ][ map[r-2][c+1] ])
break;
if(link[ map[r][c-1] ][ map[r-1][c+1] ])
break;
if(link[ map[r-1][c-1] ][ map[r][c+1] ])
break;
}
int a=map[peg[i].r][peg[i].c];
int b=map[r][c];
peg[a].connet[peg[a].pc++]=b;
peg[b].connet[peg[b].pc++]=a;
link[a][b]=link[b][a]=true;
break;
}
case 8: //330度方位
{
if(link[ map[r][c-2] ][ map[r-1][c] ])
break;
if(c-3>=0 && link[ map[r][c-3] ][ map[r-1][c-1] ])
break;
if(c+1<=n && link[ map[r][c-1] ][ map[r-1][c+1] ])
break;
if(r-2>=0)
{
if(link[ map[r-2][c-2] ][ map[r][c-1] ])
break;
if(link[ map[r-2][c-1] ][ map[r][c-2] ])
break;
if(link[ map[r-2][c] ][ map[r][c-1] ])
break;
}
if(r+1<=n)
{
if(link[ map[r-1][c-1] ][ map[r+1][c-2] ])
break;
if(link[ map[r-1][c-1] ][ map[r+1][c] ])
break;
if(link[ map[r-1][c] ][ map[r+1][c-1] ])
break;
}
int a=map[peg[i].r][peg[i].c];
int b=map[r][c];
peg[a].connet[peg[a].pc++]=b;
peg[b].connet[peg[b].pc++]=a;
link[a][b]=link[b][a]=true;
break;
}
}
}
}
}
return;
}
/*BFS,檢查先手(黑棋)是否把終域連接在一起(贏家)*/
bool CheckWin(PEG* peg,bool flag)
{
int NUM;
if(!flag) //通過(guò)舍棄最后一步棋，檢查最后一步棋是否為決定贏棋的一步
NUM=map[lastx][lasty];
for(int k=0;k<=n;k++)
{
int p=map[0][k];
if(p && p!=NUM && peg[p].color==1)
{
int queue[num];
bool vist[num]={false};
int head=0;
int tail=0;
queue[tail++]=p;
vist[p]=true;
while(head<tail)
{
int s=queue[head++];
if(peg[s].r==n)
return true;
for(int i=0;i<peg[s].pc;i++)
{
int x=peg[s].connet[i];
if(!vist[x])
{
vist[x]=true;
if(!flag && x==NUM)
continue;
queue[tail++]=x;
}
}
}
}
}
return false;
}
Sample Input
4 5
0 2 2 4 4 2 3 2 2 3
?
4 5
0 2 2 4 4 2 3 2 2 1
?
7 11
0 3 6 5 3 2 5 7 7 2 4 4 5 3 5 2 4 5 4 0 2 4
?
5 9
3 1 3 3 0 2 2 5 2 3 2 1 4 3 4 0 5 1
?
4 5
0 1 2 0 1 3 2 2 4 1
?
8 17
2 2 2 3 2 4 2 0 3 1 1 6 3 5 4 1 5 1 4 5 5 5 6 0 6 2 6 3 6 4 1 8 4 3
?
8 21
2 2 2 3 2 4 2 0 3 1 1 6 3 5 4 1 5 1 4 5 5 5 6 0 6 2 6 3 6 4 1 8 0 1 5 8 8 5 3 7 4 3
?
8 21
2 2 2 3 2 4 2 0 3 1 1 6 3 5 4 1 5 1 4 5 5 5 6 0 6 2 6 3 6 4 1 8 0 1 5 8 8 5 4 4 4 3
?
8 21
2 2 2 3 2 4 2 0 3 1 1 6 3 5 4 1 5 1 4 5 5 5 6 0 6 2 6 3 6 4 1 8 0 1 5 8 8 3 4 4 4 3
?
8 21
2 2 2 3 2 4 2 0 3 1 1 6 3 5 4 1 5 1 4 5 5 5 6 0 6 2 6 3 6 4 1 8 0 1 5 8 8 5 3 3 4 3
?
10 99
5 4 7 9 7 3 8 7 1 8 8 10 5 5 5 3 10 7 7 10 4 1 2 2 9 5 3 5 3 9 9 8 4 8 4 2 2 1 2 4 10 4 4 0 0 7 7 0 1 1 9 7 1 7 9 10 0 1 3 7 10 1 7 1 2 3 7 7 7 2 4 5 5 1 6 0 7 4 9 3 3 6 1 4 9 1 2 5 0 9 5 10 4 4 1 3 2 6 1 2 9 9 5 8 4 3 3 10 8 6 1 10 4 7 7 8 6 7 2 10 6 6 5 9 10 6 3 0 5 2 3 3 0 5 8 2 10 5 5 0 4 6 8 8 1 9 2 0 2 9 8 5 0 3 2 8 7 6 1 6 8 1 5 7 7 5 3 4 8 3 6 4 9 6 2 7 0 6 1 0 10 8 6 8 5 6 4 10 10 2 6 1 10 3 4 9 3 1
?
20 221
0 4 8 15 15 3 3 2 1 15 8 11 1 18 6 1 6 4 12 1 16 13 19 1 9 18 5 17 15 12 6 7 19 5 14 15 12 9 6 19 16 6 13 9 3 15 15 13 19 11 9 11 20 14 2 11 12 15 18 4 19 4 12 16 17 10 17 20 2 9 6 20 0 16 19 9 8 18 11 13 14 13 13 17 4 19 14 1 14 12 10 15 6 10 12 10 2 6 17 16 19 18 12 17 13 2 14 2 18 9 17 3 20 5 14 16 7 6 5 5 15 2 6 12 8 6 16 18 1 17 9 16 14 5 8 2 7 1 15 7 15 8 2 1 4 3 1 2 15 4 10 14 10 7 12 19 1 7 3 14 6 15 15 14 11 19 12 4 17 18 6 5 10 2 17 0 9 13 1 5 0 1 13 7 5 16 8 5 9 8 16 3 3 16 18 13 11 6 3 9 8 7 10 19 8 13 15 10 7 4 12 7 8 17 4 14 7 17 11 16 0 13 16 11 6 6 16 2 2 17 8 3 16 15 1 10 2 15 4 2 9 4 12 2 19 8 15 5 14 14 16 9 16 5 9 10 3 7 2 13 7 13 6 9 3 13 10 1 15 18 14 3 2 19 5 0 4 11 7 14 12 3 13 20 17 7 16 17 12 6 18 18 18 14 5 20 12 8 16 0 15 9 5 4 2 3 8 10 20 10 14 7 14 17 8 16 4 5 19 2 10 18 11 18 6 17 11 10 3 8 10 13 13 11 1 6 10 5 7 15 5 12 14 6 7 9 10 3 8 19 8 1 11 4 7 0 13 19 7 12 19 16 17 14 3 12 5 13 12 11 3 0 18 12 3 5 3 19 6 2 0 3 17 17 7 10 13 3 4 15 17 19 20 7 8 8 7 2 10 11 18 17 11 9 15 1 19 0 16 4 13 16 5 8 11 3 20 18 16 19 19 13 18 16 14 19 5 19 15 16 17 2 2 5 9 7 16 7 14 9 0 5
?
20 221
0 4 8 15 15 3 3 2 1 15 8 11 1 18 6 1 6 4 12 1 16 13 19 1 9 18 5 17 15 12 6 7 19 5 14 15 12 9 6 19 16 6 13 9 3 15 15 13 19 11 9 11 20 14 2 11 12 15 18 4 19 4 12 16 17 10 17 20 2 9 6 20 0 16 19 9 8 18 11 13 14 13 13 17 4 19 14 1 14 12 10 15 6 10 12 10 2 6 17 16 19 18 12 17 13 2 14 2 18 9 17 3 20 5 14 16 7 6 5 5 15 2 6 12 8 6 16 18 1 17 9 16 14 5 8 2 7 1 15 7 15 8 2 1 4 3 1 2 15 4 10 14 10 7 12 19 1 7 3 14 6 15 15 14 11 19 12 4 17 18 6 5 10 2 17 0 9 13 1 5 0 1 13 7 5 16 8 5 9 8 16 3 3 16 18 13 11 6 3 9 8 7 10 19 8 13 15 10 7 4 12 7 8 17 4 14 7 17 11 16 0 13 16 11 6 6 16 2 2 17 8 3 16 15 1 10 2 15 4 2 9 4 12 2 19 8 15 5 14 14 16 9 16 5 9 10 3 7 2 13 7 13 6 9 3 13 10 1 15 18 14 3 2 19 5 0 4 11 7 14 12 3 13 20 17 7 16 17 12 6 18 18 18 14 5 20 12 8 16 0 15 9 5 4 2 3 8 10 20 10 14 7 14 17 8 16 4 5 19 2 10 18 11 18 6 17 11 10 3 8 10 13 13 11 1 6 10 5 7 15 5 12 14 6 7 9 10 3 8 19 8 1 11 4 7 0 13 19 7 12 19 16 17 14 3 12 5 13 12 11 3 0 18 12 3 5 3 19 6 2 0 3 17 17 7 10 13 3 4 15 17 19 20 7 8 8 7 2 10 11 18 17 11 9 15 1 19 0 16 4 13 16 5 8 11 3 20 18 16 19 19 13 18 16 14 19 5 19 15 16 17 2 2 5 9 7 16 7 14 9 1 14
?
10 97
5 4 7 9 7 3 8 7 1 8 8 10 5 5 5 3 10 7 7 10 4 1 2 2 9 5 3 5 3 9 9 8 4 8 4 2 2 1 2 4 10 4 4 0 0 7 7 0 1 1 9 7 1 7 9 10 0 1 3 7 10 1 7 1 2 3 7 7 7 2 4 5 5 1 6 0 7 4 9 3 3 6 1 4 9 1 2 5 0 9 5 10 4 4 1 3 2 6 1 2 9 9 5 8 4 3 3 10 8 6 1 10 4 7 7 8 6 7 2 10 6 6 5 9 10 6 3 0 5 2 3 3 0 5 8 2 10 5 5 0 4 6 8 8 1 9 2 0 2 9 8 5 0 3 2 8 7 6 1 6 8 1 5 7 7 5 3 4 8 3 6 4 9 6 2 7 0 6 1 0 10 8 6 8 5 6 4 10 10 2 6 1 10 3
5 4 7 9 7 3 8 7 1 8 8 10 5 5 5 3 10 7 7 10 4 1 2 2 9 5 3 5 3 9 9 8 4 8 4 2 2 1 2 4 10 4 4 0 0 7 7 0 1 1 9 7 1 7 9 10 0 1 3 7 10 1 7 1 2 3 7 7 7 2 4 5 5 1 6 0 7 4 9 3 3 6 1 4 9 1 2 5 0 9 5 10 4 4 1 3 2 6 1 2 9 9 5 8 4 3 3 10 8 6 1 10 4 7 7 8 6 7 2 10 6 6 5 9 10 6 3 0 5 2 3 3 0 5 8 2 10 5 5 0 4 6 8 8 1 9 2 0 2 9 8 5 0 3 2 8 7 6 1 6 8 1 5 7 7 5 3 4 8 3 6 4 9 6 2 7 0 6 1 0 10 8 6 8 5 6 4 10 10 2 6 1 10 3 4 9 1 5
?
0 0
no
yes
yes
yes
no
no
yes
no
yes
no
yes
yes
no
no
no
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
