首页 > 搜索 > BFS搜索 > POJ 2619 Delta-wave [解题报告] Java
2013
11-11

POJ 2619 Delta-wave [解题报告] Java

Delta-wave

问题描述 :

A triangle field is numbered with successive integers in the way shown on the picture below.

The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the traveller passes makes the length of the traveller’s route.

Write the program to determine the length of the shortest route connecting cells with numbers N and M.

输入:

Input contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).

输出:

Output should contain the length of the shortest route.

样例输入:

6 12 

样例输出:

3

解题代码:

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

 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
 
	int a,b;
       a=sc.nextInt();
       b=sc.nextInt();
	int p1,p2,p3,d1,d2,d3;
	p1=(int)Math.sqrt(a*1.0);
	if(p1*p1< a) p1++;
	d1=(int)Math.sqrt(b*1.0);
	if(d1*d1< b) d1++;
	int v1=(p1-1)*(p1-1);
	int v2=(d1-1)*(d1-1);
	p2=(a-v1+1)/2;
	d2=(b-v2+1)/2;
	p3=(p1*p1-a)/2+1;
	d3=(d1*d1-b)/2+1;
	int ans=Math.abs(p1-d1)+Math.abs(p2-d2)+Math.abs(p3-d3);
	System.out.printf("%d\n",ans);
 }
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。