2013
11-11

Connect

 Figure 1 Figure 2 Figure 3a Figure 3b Figure 4

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 output contains one line for each data set: “yes” if the last move is a winning move and “no” otherwise.

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

public static final int a[][] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
static int n ;
public static final int sx0[][] = {{-2,0},{-2,1},{-1,0},{-1,1},{-1,0},{-1,-1},{-1,1},{-1,1},{-2,2}};
public static final int sy0[][] = {{0,1},{0,2},{1,1},{1,2},{0,2},{0,1},{0,3},{1,0},{0,1}};

public static final int sx1[][] = {{0,1},{0,2},{1,1},{1,2},{-1,1},{0,1},{1,1},{0,-1},{1,0}};
public static final int sy1[][] = {{1,-1},{1,0},{2,-1},{2,0},{1,0},{2,0},{3,0},{1,1},{2,2}};

public static final int s[][] = {{-1,-1},{-1,1},{1,1},{-1,1},{1,1},{1,-1},{-1,-1},{1,-1}};

static int cx[] ;
static int cy[] ;

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

while(true){
n = scan.nextInt();
int m = scan.nextInt();

if(n == 0&& m==0)
break;

cx = new int[m];
cy = new int[m];
int map[][] = new int[n+1][n+1];
for(int i=0;i<=n;i++)
java.util.Arrays.fill(map[i], -1);

for(int d=0;d< m;d++){
int y = scan.nextInt();
int x = scan.nextInt();
map[x][y] = d;
cx[d] = x;
cy[d] = y;

}

boolean flag1 = false;
boolean flag2 = false;
for(int i=0;i<=n;i++){
flag1 = true;
break;
}
}
if(!flag1){
System.out.println("no");
continue;
}

for(int i=0;i<=n;i++){
flag2 = true;
break;
}
}
if(flag2)
System.out.println("no");
else
System.out.println("yes");

}

}

public static boolean bfs(int v,boolean[][] link,int m) {

Queue< Integer> q = new LinkedList< Integer>();
boolean visit[] = new boolean[m];
visit[v] = true;
while(!q.isEmpty()){
v = q.poll();
for(int i=0;i< m;i++){
if(cy[i]==n)
return true;
visit[i] = true;
}
}
}

return false;
}

public static void drawLine(boolean[][] link, int[][] map,int xs,int ys) {

for(int i=0;i< 8;i++){

int x = xs + a[i][0];
int y = ys + a[i][1];

if(i==2||i==3||i==6||i==7){
int k ;
for(k=0;k< 9;k++){
int xa = xs + s[i][0]*sx0[k][0];
int ya = ys + s[i][1]*sx0[k][1];

int xb = xs + s[i][0]*sy0[k][0];
int yb = ys + s[i][1]*sy0[k][1];
if(check(xa,ya)&&check(xb,yb)&&map[xa][ya]!=-1
break;
}
}
if( k == 9){
}

}else{
int k ;
for(k=0;k< 9;k++){
int xa = xs + s[i][0]*sx1[k][0];
int ya = ys + s[i][1]*sx1[k][1];

int xb = xs + s[i][0]*sy1[k][0];
int yb = ys + s[i][1]*sy1[k][1];
if(check(xa,ya)&&check(xb,yb)&&map[xa][ya]!=-1&&
break;
}
}
if( k == 9){
}

}

}

}

}

public static boolean check(int a, int b) {

return a>=0&&b>=0&&a<=n&&b<=n;
}
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

2. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge