SkipStones
Problem Statement 問題描述
When a stone is thrown across water, sometimes it will land on the water and bounce rather than falling in right away. Suppose that a stone is thrown a distance of n. On each successive bounce it will travel half the distance as the previous bounce (rounded down to the nearest integer). When it can not travel any further, it falls into the water. If, at any point, the stone lands on an obstruction rather than water, it will not bounce, but will simply deflect and fall into the water. Please look at the figure for further clarification (with black, red and green cells representing banks, obstructions and free water respectively). So, if the stone is thrown a distance 7, it will bounce and travel a distance of 3, then finally a distance of 1, having travelled a total distance of 11 (the green path in the figure). If a stone is thrown a distance of 8, it will reach the opposite bank, and if thrown at distances of 2 or 6 it will hit an obstruction during its travel. These are the three red paths in the figure.
You are given a String water. An ‘X’ represents an obstruction, while a ‘.’
represents water free from obstruction. You are to return an int representing
the maximum distance a stone can travel and finally fall in the water, without
hitting any obstructions, and without reaching the opposite bank (going beyond
the end of the string). You may choose any initial distance for the throw,
which starts from the left side of the string. A distance of 1 is the first
character of the string, etc. If no initial throw will result in the stone
landing in the water without hitting an obstruction, return 0.
給予一個(gè) String 輸入：water. 其內(nèi)’X'字符代表礁石，’.’ 代表無礁石水面。你的程序
返回一個(gè)整數(shù)int，表示該石頭在最終落入水中的情況下運(yùn)行的總最大距離，觸礁、撞岸的
情形都必須排除。其中撞岸表征為 (字符串訪問越上界). 你可以選擇任何初始的投擲距離
，出發(fā)點(diǎn)為字符串最左側(cè)。距離為1則抵達(dá)字符串的第一個(gè)字符，依此類推。如果沒有投擲
距離，石頭被當(dāng)作直接入水，返回量為0。
定義：
Class:
SkipStones
Method:
maxDistance
Parameters:
String
Returns:
int
Method signature:
int maxDistance(String water)
(確保你的函數(shù)為公共類型 public)
注：
礁石處在水面，所以不存在石頭入水后撞礁的情形。
限制條件：-
water 字符串包含1到50個(gè)元素[即礁石或水面]，1、50包含在內(nèi)。
water的每個(gè)元素包含1到50個(gè)字符, 1、50包含在內(nèi)。
water的每個(gè)元素的每個(gè)字符要么是’X'，要么是 ‘.’.
測試?yán)?/P>
0)
“..X…..X…”
返回: 11
該例正如題目中（綠色軌跡）所圖示。
1)
“…X…”
返回: 3
假如沒有該礁石,可以扔一距離4,從而總距離為7。但在有礁石情形下，最佳則是扔出距離2
，再跳1而停止。
2)
“….X….X…XXXX.X…..”
返回: 22
12 + 6 + 3 + 1 = 22, 為最佳結(jié)果.
3)
“XXXXXXX.XXX.X..”
返回: 15