首页 > 专题系列 > Java解POJ > POJ 1574 The Triangle Game [解题报告] Java
2013
11-09

POJ 1574 The Triangle Game [解题报告] Java

The Triangle Game

问题描述 :



In the triangle game you start off with six triangles numbered on each edge, as in the example above. You can slide and rotate the triangles so they form a hexagon, but the hexagon is only legal if edges common to two triangles have the same number on them. You may not flip any triangle over. Two legal hexagons formed from the six triangles are illustrated below.



The score for a legal hexagon is the sum of the numbers on the outside six edges. Your problem is to find the highest score that can be achieved with any six particular triangles.

输入:

The input will contain one or more data sets. Each data set is a sequence of six lines with three integers from 1 to 100 separated by blanks on each line. Each line contains the numbers on the triangles in clockwise order. Data sets are separated by a line containing only an asterisk. The last data set is followed by a line containing only a dollar sign.

输出:

For each input data set, the output is a line containing only the word “none” if there are no legal hexagons or the highest score if there is a legal hexagon.

样例输入:

1 4 20
3 1 5
50 2 3
5 2 7
7 5 20
4 7 50
*
10 1 20
20 2 30
30 3 40
40 4 50
50 5 60
60 6 10
*
10 1 20
20 2 30
30 3 40
40 4 50
50 5 60
10 6 60
$

样例输出:

152
21
none

解题代码:

/* @author: */
import java.util.*;

public class Main {
  private int x[];
  private int y[];
  private int z[];
  private int a[]=new int[7],b[]=new int[7],c[]=new int[7],ax[]=new int[7],use[]=new int[7];
  private int max;

 public Main(int x[],int y[],int z[]){
    this.x=x;
    this.y=y;
    this.z=z;
    max=0;
   for(int i = 0;i < 7;i ++) use[i] = 0;
  }

public int  dfs(int p){
for(int i = 1;i <= 6;i ++) //每个三角形有6种放法
{
   if(use[i]!=0) continue;//前面三角形放过的位置不等再放
   for(int j = 1;j <= 3;j ++)//每个三角形又可进行旋转
   {
    if(j == 1) {a[p] = x[i];b[p] = y[i];c[p] = z[i];}
    if(j == 2) {a[p]=y[i];b[p]=z[i];c[p] = x[i];}
    if(j == 3) {a[p] = z[i];b[p] = x[i];c[p] = y[i];}
    if(p != 1 && c[p] != b[p-1]) //这点很关键,必须边长相等
     continue;
    if(p == 1)
     ax[p] = a[p];
    else
     ax[p] = ax[p-1] + a[p];
    use[i] = 1;
    if(p< 6)
     dfs(p + 1);
    else
    {
     if(b[p] == c[1]) // 同上,这点容易忽视
     {
      if(max < ax[p]) 
       max = ax[p];//取最优值
     }
    }
   }
   use[i] = 0;
}
 return max;
}

  public static void main(String[] args){
   Scanner in = new Scanner(System.in);
   char ch;
   int x[]=new int[7],y[]=new int[7],z[]=new int[7];
   while(in.hasNext()){
   
   for(int i = 1;i <= 6;i ++) {
    x[i]=in.nextInt();
    y[i]=in.nextInt();
    z[i]=in.nextInt();
   }
    
    Main m=new Main(x,y,z);
   int max=m.dfs(1);
   if(max == 0)
    System.out.printf("none\n");
   else
    System.out.printf("%d\n",max);
    ch=in.next().charAt(0);
   if(ch=='$')
       break;
  }
 }
}

  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept