首页 > 专题系列 > Java解POJ > POJ 2706 Connect [解题报告] Java
2013
11-11

POJ 2706 Connect [解题报告] Java

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];  
            boolean link[][] = new boolean[m][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;  
                drawLine(link,map,x,y);  
                  
            }  
              
              
              
            boolean flag1 = false;  
            boolean flag2 = false;  
            for(int i=0;i<=n;i++){  
                if(map[i][0]%2==0&&bfs(map[i][0],link,m)){  
                    flag1 = true;  
                    break;  
                }  
            }  
            if(!flag1){  
                System.out.println("no");  
                continue;  
            }  
              
            for(int i=0;i<=n;i++){  
                if(map[i][0]%2==0&&map[i][0]!=m-1&&bfs(map[i][0],link,m-1)){  
                    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>();  
        q.add(v);  
        boolean visit[] = new boolean[m];  
        visit[v] = true;  
        while(!q.isEmpty()){  
            v = q.poll();  
            for(int i=0;i< m;i++){  
                if(!visit[i]&&link[v][i]){  
                    if(cy[i]==n)  
                        return true;  
                    q.add(i);  
                    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(x>=0&&x<=n&&y>=0&&y<=n&&map[x][y]%2==map[xs][ys]%2&&!link[map[x][y]][map[xs][ys]]){  
                  
                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 
                            &&map[xb][yb]!=-1&&link[map[xa][ya]][map[xb][yb]]){  
                            break;  
                        }  
                    }  
                    if( k == 9){  
                        link [map[x][y]][map[xs][ys]] = true;  
                        link [map[xs][ys]][map[x][y]] = true;  
                    }  
                      
                }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&&
	map[xb][yb]!=-1&&link[map[xa][ya]][map[xb][yb]]){  
                            break;  
                        }  
                    }  
                    if( k == 9){  
                        link [map[x][y]][map[xs][ys]] = true;  
                        link [map[xs][ys]][map[x][y]] = true;  
                    }  
                      
                }  
                  
            }  
              
        }  
          
    }  
  
    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