POJ2706-Connect - 军军小站|张军博客

转载请注明出处：優 YoU http://user.qzone.qq.com/289065406/blog/1308890557

大致题意：

一种类似围棋的游戏，有黑白两种颜色的棋子。

规定黑棋为先手，白棋为后手。

放下棋子 A 后，若 A 的 8 个马步方位（即中国象棋的“马”或国际象棋的“骑士”的“日”字走法）至少存在 1 个同色的棋子，且当连接 A 与这些棋子时，其连线不切割已经有的线，则连接。

黑棋的目标是连出一条从 X 轴的 0 列到 N 列的路；

白棋的目标是连出一条从 Y 轴的 0 行到 N 行的路。

就是说某一方要赢棋，当且仅当其把自己的两个“终域”连接在一起，完全阻隔对方的连接。

按照以上规则，判断黑棋所走的最后一步是否为赢棋的一步。

解题思路：

比较麻烦的模拟，但是难度不大，难点主要在于判断连线是否相交。

如上图放下一只棋子后，先检查其附近的 8 个方位是否存在同色棋子，若存在，则检查是否允许与该同色棋子连线。

检查连线方法如下图，以 30 度的方位为例：

如上图，当放下新棋子后，若检测到 30 度方位存在与其同色的棋子，则在连接蓝线之前，先检查是否已存在 9 条红色的线，当且仅当这 9 条红线都不存在时，才允许连接蓝线。

其他 7 个方位也是同样做法。

最后要判断黑棋的最后一步是不是为赢棋的一步，只需要做两次 BFS 。

第一次 BFS ：以黑棋的 0 终域为起点，寻找是否存在到 N 终域的路。

第二次 BFS ：先删去最后一步棋，再以黑棋的 0 终域为起点，寻找是否存在到 N 终域的路。

当第一次 BFS 结果为 true ，第二次 BFS 结果为 false 时，则说明黑棋的最后一步为赢棋的一步。

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]; //对坐标为(x,y)的棋子编号 bool link[num][num]; //标记某两个编号的棋子是否有连线 int posx[]={0,-1,-2,-2,-1,1,2,2,1}; //对应于(x,y)的八个方位 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]; //记录与当前棋子直接相连的棋子编号 int pc; //connet的指针 chess() { color=-1; pc=0; } }PEG; void LinePeg(PEG* peg,int i); //把棋子peg[i]与与其相邻的八个方位的同色棋子连线 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; //编号记录 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)与与其相邻的八个方位的同色棋子连线*/ 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) //"日"字对角连线 { 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) //通过舍弃最后一步棋，检查最后一步棋是否为决定赢棋的一步 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

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 1 5

0 0

Sample Output
no
yes
yes
yes
no
no
yes
no
yes
no
yes
yes
no
no
no

POJ2706-Connect

更多文章、技术交流、商务合作、联系博主

微信扫码或搜索：z360901061

微信扫一扫加我为好友

QQ号联系： 360901061

您的支持是博主写作最大的动力，如果您喜欢我的文章，感觉我的文章对您有帮助，请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧，狠狠点击下面给点支持吧，站长非常感激您！手机微信长按不能支付解决办法：请将微信支付二维码保存到相册，切换到微信，然后点击微信右上角扫一扫功能，选择支付二维码完成支付。

【本文对您有帮助就好】元

2元

5元

10元

20元

自定义