?

?

知識要點

　　首先介紹一下曼哈頓，曼哈頓是一個極為繁華的街區，高樓林立，街道縱橫，從A地點到達B地點沒有直線路徑，必須繞道，而且至少要經C地點，走AC和 CB才能到達，由于街道很規則，ACB就像一個直角3角形，AB是斜邊，AC和CB是直角邊，根據畢達格拉斯(勾股)定理，或者向量理論，都可以知道用AC和CB可以表達AB的長度。

　　在早期的計算機圖形學中，屏幕是由像素構成，是整數，點的坐標也一般是整數，原因是浮點運算很昂貴，很慢而且有誤差，如果直接使用AB的距離，則必須要進行浮點運算，如果使用AC和CB，則只要計算加減法即可，這就大大提高了運算速度，而且不管累計運算多少次，都不會有誤差。因此，計算機圖形學就借用曼哈頓來命名這一表示方法。

　　曼哈頓距離：兩點在南北方向上的距離加上在東西方向上的距離，即d（i，j）=|x_i-x_j|+|y_i-y_j|。對于一個具有正南正北、正東正西方向規則布局的城鎮街道，從一點到達另一點的距離正是在南北方向上旅行的距離加上在東西方向上旅行的距離。

　　通過分析下面的題目，可知其可以應用曼哈頓距離計算至(1,1)點最近的點，依據曼哈頓距離即可計算出結果值。

　　代碼如下：

1 /** 2 * 解救小易 3 有一片1000*1000的草地，小易初始站在(1,1)(最左上角的位置)。小易在每一秒會橫向或者縱向移動到相鄰的草地上吃草(小易不會走出邊界)。 4 大反派超超想去捕捉可愛的小易，他手里有n個陷阱。第i個陷阱被安置在橫坐標為xi ，縱坐標為yi 的位置上，小易一旦走入一個陷阱，將會被超超捕捉。 5 你為了去解救小易，需要知道小易最少多少秒可能會走入一個陷阱，從而提前解救小易。 6 輸入描述: 7 第一行為一個整數n(n ≤ 1000)，表示超超一共擁有n個陷阱。 8 第二行有n個整數xi，表示第i個陷阱的橫坐標 9 第三行有n個整數yi，表示第i個陷阱的縱坐標 10 保證坐標都在草地范圍內。 11 12 輸出描述: 13 輸出一個整數,表示小易最少可能多少秒就落入超超的陷阱 14 15 輸入例子: 16 3 17 4 6 8 18 1 2 1 19 輸出例子: 20 3 21 思路: 22 計算最短距離 23 */ 24 25 #include <iostream> 26 #include <vector> 27 using namespace std; 28 29 int main(void){ 30 int trapNum; 31 32 while (cin >> trapNum){ 33 if (trapNum <= 0 || trapNum > 1000) 34 continue; 35 // vector<int> dx; 36 // vector<int> dy; 37 vector<int> dx(trapNum);//指定容器大小，否則會溢出 38 vector<int> dy(trapNum); 39 for (int i = 0; i < trapNum; i++) 40 cin >> dx[i]; 41 for (int i = 0; i < trapNum; i++) 42 cin >> dy[i]; 43 44 int result = 99999; 45 //枚舉一遍維護最小值 46 for (int i = 0; i < trapNum; i++){ 47 int length = (dx[i] - 1) + (dy[i] - 1); 48 if (length < result) 49 result = length; 50 } 51 cout << result << endl; 52 } 53 return 0; 54 }

?

總結

以上是生活随笔為你收集整理的剑指Offer——网易笔试之解救小易的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。