HDU 1030 Delta-wave 數學題解

Delta-wave

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5782    Accepted Submission(s): 2204

Problem Description 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 Input contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).  

Output Output should contain the length of the shortest route.  

Sample Input

6 12 
        

Sample Output

3
  
  

        

一條可以利用建立坐标系做的題目。

引用：http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=18719&messageid=1&deep=0

我們把上下兩個相連的三角形構成的菱形看做一個格，左斜線看做橫坐标，右斜線看做縱坐标，也是四個方向(0,-1),(0,1),(-1,0),(1,0)變化，那麼就相當于直角坐标了。

從(x1,y1)到(x2,y2)，這是斜角坐标，距離dis=abs(x1-x2)+abs(y1-y2);我們還需要考慮菱形中的移動，這個都是一層移動一次。

是以答案ans=dis+abs(a-b)=abs(x1-x2)+abs(y1-y2)+abs(a-b)，其中a和b表示各自層數，x1,y1,x2,y2表示兩個數所在菱形在斜角坐标系的位置。      

利用這個思路寫程式就很簡單的了。

不過為什麼這樣會正确？好像還是很難解析清楚，我了解這是一個規律，跨過了兩個不同的斜邊，就會得到最短的路徑了，因為本題一定要走邊，不能走頂點跨到下一個三角形的，故此上下左右的邊的最小相隔邊數，就是題目要求的最短距離數了。也就可以想象為跨過三角形的三個邊，三個方向的邊，剛好是上下的h高度邊，左斜線的x邊，右斜線的y邊，（有人也喜歡用x，y，z）那麼就肯定是最短路徑了。

也可以直接利用數學的方法，然後加點暴力法算出來的，之前做過，不重複了。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <math.h>
using namespace std;

int main()
{
	int n, m;
	while (scanf("%d %d", &n, &m) != EOF)
	{
		int nh = (int)sqrt(double(n-1));
		int mh = (int)sqrt(double(m-1));

		int nx = (n - nh*nh - 1) >> 1;
		int mx = (m - mh*mh - 1) >> 1;

		int ny = ((nh + 1) * (nh + 1) - n) >> 1;
		int my = ((mh + 1) * (mh + 1) - m) >> 1;

		printf("%d\n", abs(nh-mh) + abs(nx-mx) + abs(ny-my));
	}
	return 0;
}