首页 > ACM题库 > HDU-杭电 > hdu 2727 Connect[解题报告]hoj
2014
02-14

hdu 2727 Connect[解题报告]hoj

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)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮