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

POJ 2362 Square [解题报告] Java

Square

问题描述 :

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

输入:

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

输出:

For each case, output a line containing “yes” if is is possible to form a square; otherwise output “no”.

样例输入:

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

样例输出:

yes
no
yes

解题代码:

import java.io.*;
import java.util.*;

public class Main {

//璁板��板�����垮害��
int totalNum;
//璁板���釜�板�������缁��
int[] numArr;
//璁板�姣�釜灏��妫�����浣跨�杩��
boolean[] used;

public static void main(String args[]) throws Exception {
   Main m=new Main();
   m.begin();
}

private void begin() throws Exception {
   Scanner cin = new Scanner(System.in);
   int totalLine = cin.nextInt();
   for(int i=0; i< totalLine; i++){
    totalNum = cin.nextInt();
    numArr = new int[totalNum];
    //�婚�搴��
    int sumLen = 0;
    for(int j=0; j< totalNum; j++){
     numArr[j] = cin.nextInt();
     sumLen += numArr[j];
    }
    //������涓������芥病琚�娇�ㄨ���
    used = new boolean[totalNum];
    for(int j=0; j< totalNum; j++)
     used[j] = false;
    //���椤绘� 4 ����般�
    if(sumLen%4==0){
     //���锛��搴��
     Arrays.sort(numArr);
     int temp;
     for(int k=0; k< totalNum/2; k++){
      temp = numArr[k];
      numArr[k] = numArr[totalNum-1-k];
      numArr[totalNum-1-k] = temp;
     }
     //�峰���ぇ�笺�
     int maxNum = numArr[0];
     //��疆宸茬��煎ソ��竟�颁负 0��
     passNum = 0;
     //��ぇ�间��藉ぇ浜���跨� 1/4��
     if(maxNum <= sumLen/4){
      //寮��娣卞害浼����储��
      if(DFS(0, sumLen/4, 0))
       System.out.println("yes");
      else
       System.out.println("no");
     }else
      System.out.println("no");
    }else
     System.out.println("no");
   }
}

//璁板�宸茬��煎�������搴��杈圭�涓��锛��澶�4 涓��
int passNum = 0;
//�����������惊������绗��瑕��璇���垮害���瑕��涓��搴����
private boolean DFS(int f_num, int f_len, int f_sum){
   //褰���板�������搴��绛����
   if(f_len == f_sum){
    //澧��涓�������竟�般�
    passNum++;
    //��疆搴�����濮�����绗��
    f_sum = 0;
    f_num = 0;
    //褰��杩��杈规���4 �哥�灏辫�������
    if(passNum == 4)
     return true;
   }
   //寮�����涓��灞��
   for(int i=f_num; i< totalNum; i++){
    //褰���板�涓���板�浜��浜��瑕���垮害�讹�骞朵����娌¤�浣跨���
    if(f_sum+numArr[i]<=f_len && !used[i]){
     //���璁板�涓哄凡缁�娇�ㄣ�
     used[i] = true;
     //杩��涓��娆$������
     DFS(i+1, f_len, f_sum+numArr[i]);
     //杈规�杈惧� 4 �����烦�哄惊���
     if(passNum == 4)
      break;
     //���浜���㈢����锛����竟�版病��揪��4锛������煎�涓��杈癸��������¤竟锛�互渚挎�璇��浠��缁����
     if(f_sum+numArr[i] == f_len)
      passNum--;
     //���������褰��
     used[i] = false;
    }
   }
   //����舵��ヤ�娆℃����濂芥��瑰舰��
   if(passNum == 4)
    return true;
   //杩��澶辫触��
   return false;
}
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?