首页 > ACM题库 > POJ 1576 Colorville [解题报告] Java
2013
11-09

POJ 1576 Colorville [解题报告] Java

Colorville

问题描述 :

A simple matching game for children uses a board that is a sequence of colored squares. Each player has a game piece. Players alternate turns, drawing cards containing either one colored square or two colored squares of the same color. Players move their pieces forward on the board to the next square that matches the single color on the card, or forward to the second matching square if the card contains two colored squares, or forward to the last square on the board if there is no square matching the description above. A player wins if his piece lands on the last square of the board. It is possible for all the cards to be drawn and still not have a winner.

This problem represents colors with capital letters from A-Z. Below is a diagram of a sample board.



Consider the deck of cards: R, B, GG, Y, P, B, P, RR

For 3 players, the game proceeds as follows:

Player 1 draws R, moves to 1st square

Player 2 draws B, moves to 5th square

Player 3 draws GG, moves to 8th square

Player 1 draws Y, moves to 2nd square

Player 2 draws P, moves to 11th square

Player 3 draws B, moves to 9th square

Player 1 draws P, moves to 4th square

Player 2 draws RR, Wins! (no Rs in front of piece so it goes to last square)

Using the same board and the same deck of cards, but with 2 players, Player 1 wins after 7 cards. With 4 players, no one wins after exhausting the deck of 8 cards.

输入:

Input consists of information for one or more games. Each game starts with one line containing the number of players (1-4), the number of squares on the board (1-79), and the number of cards in the deck (1-200). This is followed by a single line of characters representing the colored squares on the board. Following this are the cards in the deck, one card per line. Cards can have only a single character, or two of the same character. The end of the input is signalled by a line with 0 for the number of players – the other two values will be present but indeterminate.

输出:

For each game, the output is either the winning player and the total number of cards drawn, or the number of cards in the deck, as shown in the sample output. Always use the plural “cards”.

样例输入:

2 13 8
RYGPBRYGBRPOP
R
B
GG
Y
P
B
P
RR
2 6 5
RYGRYB
R
YY
G
G
B
3 9 6
QQQQQQQQQ
Q
QQ
Q
Q
QQ
Q
0 6 0

样例输出:

Player 1 won after 7 cards.
Player 2 won after 4 cards.
No player won after 6 cards.

解题代码:

/* @author:[email protected] */
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
 public static void main(String[] args) throws Exception{
   BufferedReader br = new BufferedReader(new
               InputStreamReader(System.in));
   String s,board;
   String[] ss;
   int n;
   int[] p;
   boolean flag=false;
   while((s=br.readLine())!=null&&!s.startsWith("0")){
	ss=s.split(" ",3);
	p=new int[parseInt(ss[0])];
	for(int i=0;i< p.length;i++)
         p[i]=-1;
	n=parseInt(ss[2]);
	board=br.readLine();
	for(int i=0;i< n;i++){
	  s=br.readLine();
	  if(flag)continue;
	  if(win(p,board,s,i)){
	    flag=true;
	    System.out.println("Player "+(i%p.length+1)+" won after "+(i+1)+" cards.");
	  }
	}
	if(flag){
	  flag=false;
	}else{
	  System.out.println("No player won after "+n+" cards.");
       }
    }
    br.close();
   }


 static int parseInt(String s){
   int t = 0;
   for(char ch: s.toCharArray()){
      t *= 10;
      t += ch-'0';
   }
   return t;
 }

 static boolean win(int[] p,String board,String instruction,int n){
		
   int pos=n%p.length;
   char target=instruction.charAt(0);
   try {
	for(int i=0;i< instruction.length();i++){
	 do{
           p[pos]++;
	  }while(board.charAt(p[pos])!=target);
      } 
   }catch(StringIndexOutOfBoundsException e) {
	return true;
   }
   return p[pos]==board.length()-1;
  }
}

  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义

  4. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }