2014
02-14

# Connect

Your task is to decide if a specified sequence of moves in the board game Twixt ends with a winning move. In this version of the game, different board sizes may be specified. Pegs are placed on a board at integer coordinates in the range [0, N]. Players Black and White use pegs of their own color. Black always starts and then alternates with White, placing a peg at one unoccupied position (x,y). Black’s endzones are where x equals 0 or N, and White’s endzones are where y equals 0 or N. Neither player may place a peg in the other player’s endzones. After each play the latest position is connected by a segment to every position with a peg of the same color that is a chess knight’s move away (2 away in one coordinate and 1 away in the other), provided that a new segment will touch no segment already added, except at an endpoint. Play stops after a winning move, which is when a player’s segments complete a connected path between the player’s endzones.
For example Figure 1 shows a board with N=4 after the moves (0,2), (2,4), and (4,2). Figure 2 adds the next move (3,2).
Figure 3a shows a poor next move of Black to (2,3). Figure 3b shows an alternate move for Black to (2,1) which would win the game.
Figure 4 shows the board with N=7 after Black wins in 11 moves:
(0, 3), (6, 5), (3, 2), (5, 7), (7, 2), (4, 4), (5, 3), (5, 2), (4, 5), (4, 0), (2, 4).

The input contains from 1 to 20 datasets followed by a line containing only two zeroes, "0 0". The first line of each dataset contains the maximum coordinate N and the number of total moves M where 3 < N < 21, 4 < M < 250, and M is odd.
The rest of the dataset contains a total of M coordinate pairs, with one or more pairs per line. All numbers on a line will be separated by a space. M being odd means that Black will always be the last player. All data will be legal. There will never be a winning move before the last move.

The input contains from 1 to 20 datasets followed by a line containing only two zeroes, "0 0". The first line of each dataset contains the maximum coordinate N and the number of total moves M where 3 < N < 21, 4 < M < 250, and M is odd.
The rest of the dataset contains a total of M coordinate pairs, with one or more pairs per line. All numbers on a line will be separated by a space. M being odd means that Black will always be the last player. All data will be legal. There will never be a winning move before the last move.

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
0 0

no
yes
yes

#include<stdio.h>
#include<iostream>
#include<memory.h>
#include<vector>
#include<string>
using namespace std;
int dir[8][2]={-1,-2,-1,2,1,-2,1,2,-2,-1,-2,1,2,-1,2,1};
int n;
struct pt
{
int x,y;
pt(){}
pt(int xx,int yy){x=xx;y=yy;}
};
struct seg
{
pt p1,p2;
seg(pt pp1,pt pp2){p1=pp1;p2=pp2;}
};
int cross(pt a,pt b)
{
return a.x*b.y-a.y*b.x;
}
int cross(pt a,pt b,pt c)
{
return cross(pt(a.x-c.x,a.y-c.y),pt(b.x-c.x,b.y-c.y));
}
vector<seg> SEG;
int visited[100][100];
vector<int> g[1001];
bool SegCross(seg s1,seg s2)
{
if ((cross(s1.p1,s2.p1,s1.p2)*cross(s1.p1,s2.p2,s1.p2)<0)
&& (cross(s2.p1,s1.p1,s2.p2)*cross(s2.p1,s1.p2,s2.p2)<0))
return true;
else return false;
}
bool judge(seg l)
{
int i,j;
for(i=0;i<SEG.size();i++)
if (SegCross(l,SEG[i])) return false;
return true;
}
bool vtd[20000];
bool dfs(int x)
{
int i;
if (x/25==n) return true;
if (vtd[x]) return false;
vtd[x]=true;
for(i=0;i<g[x].size();i++)
{
if (dfs(g[x][i])) return true;
}
return false;
}
bool is_win()
{
int i;
memset(vtd,0,sizeof(vtd));
for(i=0;i<=n;i++)
{
if (dfs(i)) return true;
}
return false;
}

int main()
{
int m,i,j,color,x,y;
bool fl;
while(cin>>n>>m)
{
if (n==0) break;
SEG.clear();
memset(visited,0,sizeof(visited));
for(i=0;i<=1000;i++) g[i].clear();
color=1;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
visited[x][y]=color;
int xx,yy;
for(j=0;j<8;j++)
{
xx=x+dir[j][0];
yy=y+dir[j][1];
if ((xx>=0)&&(xx<=n)&&(yy>=0)&&(yy<=n))
if (visited[xx][yy]==color)
if ( judge(seg(pt(x,y),pt(xx,yy))) )
{
//	 cout<<x<<' '<<y<<endl;
//		 cout<<xx<<' '<<yy<<endl;
SEG.push_back(seg(pt(x,y),pt(xx,yy)));
g[x*25+y].push_back(xx*25+yy);
g[xx*25+yy].push_back(x*25+y);
}
}
//	 cout<<SEG.size()<<endl;
color=3-color;
}
if (is_win()) printf("yes\n");
else printf("no\n");
}

}

1. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮