首页 > 专题系列 > Java解POJ > POJ 1063 Flip and Shift [解题报告] Java
2013
11-09

POJ 1063 Flip and Shift [解题报告] Java

Flip and Shift

问题描述 :

This puzzle consists of a random sequence of m black disks and n white disks on an oval-shaped track, with a turnstile capable of flipping (i.e., reversing) three consecutive disks. In Figure 1, there are 8 black disks and 10 white disks on the track. You may spin the turnstile to flip the three disks in it or shift one position clockwise for each of the disks on the track (Figure 1).



The goal of this puzzle is to gather the disks of the same color in adjacent positions using flips and shifts. (Figure 2)



You are to write a program which decides whether a given sequence can reach a goal or not. If a goal is reachable, then write a message “YES”; otherwise, write a message “NO”.

输入:

The input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each of the next T lines gives a test case. A test case consists of an integer, representing the sum of m and n, and a sequence of m+n 0s and 1s, representing an initial sequence. A 0 denotes a white disk and a 1 denotes a black disk. The sum of m and n is at least 10 and does not exceed 30. There is a space between numbers.

输出:

The output should print either “YES” or “NO” for each test case, one per line.

样例输入:

2 
18 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1 
14 1 1 0 0 1 1 1 0 0 1 1 0 1 0 

样例输出:

YES
NO

解题代码:

//* @author:
import java.util.Scanner;
public class Main{

 public static void main(String args[])
{
  int cas, i, n, j, s1, s2;
  int a[]=new int[30];
  Scanner sc=new Scanner(System.in);
  cas=sc.nextInt();
	
  while((cas--)!=0 )
  {
   n=sc.nextInt();
		
   for( i=0; i< n; i++ )
   {
      a[i]=sc.nextInt();
   }

   for( i=0; i< n; i++ )
    if( a[i] == 1 )
    {
	s1 = s2 = 0;
	for( j=1; j< n; j++ )
	if( a[(j+i)%n] == 1 )
	{
	   if( j%2!=0 ) s1++;
	   else s2++;
	}
	if( s1 == s2 || s1 == s2+1 )
	{
	   System.out.printf( "YES\n" );
	   break;
	}
      }
		
     if( i >= n )
	System.out.printf( "NO\n" );
   }
  }
}

  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])