There is an island which is represented by square matrix NxN. A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies. Let island is represented as (0,0) to (N-1,N-1) (i.e NxN matrix) & person is standing at given co-ord…

gistfile1.md

###死亡小岛

####原题

一个小岛，表示为一个N×N的方格，从(0,0)到(N-1, N-1)，一个人站在岛上，位置(x, y)，他可以上下左右走，一步一个格子，他选择上下左右的可能性是一样的。当他走出小岛，就意味着死亡。假设他要走n步，请问他死亡的概率有多大？请写出求解代码。

####分析 遇到这样的问题，就试着走几步好了。当一个人在(x,y)的时候，假设他此时，死亡的概率为p(x,y,n)，然后，他有四种选择，而且是可能性相同，就是说，选择上下左右的概率都是1/4：

• 选择上边，死亡的概率是多少呢？此时位置为(x, y-1)，剩余的步数为n-1,则概率为p(x, y - 1, n - 1)
• 选择下边同理：概率为p(x, y + 1, n - 1)
• 选择左边同理：概率为p(x - 1, y, n - 1)
• 选择右边同理：概率为p(x + 1, y, n - 1)

则，p(x,y,n)=(p(x, y - 1, n - 1) + p(x, y + 1, n - 1) + p(x - 1, y, n - 1) + p(x + 1, y, n - 1))/4，可以表达出递归的形式。

这个题目，看似比较复杂，但是尝试走一步，之后，写出递归表达式了，就比较简单了。递归终止的条件，只要x或者y，满足了小于0或者大于n-1的时候，p=1。

import java.util.*;

class ProbabilityOfAlive
{
  public static double probabilityOfAlive(int x, int y, int n)
  {
    if (x < 0 || x > (n - 1) || y < 0 || y > (n - 1) || n < 1) {return 0.0;}
    return probabilityOfAlive(x, y, n, n, new HashMap<String, Double>());
  }

  private static double probabilityOfAlive(int x, int y, int n, int step, HashMap<String, Double> map)
  {
    if (0 == step) {return 1.0;}
    // if the state is already calculated, return from HashMap
    String key = "";
    {
      StringBuffer sb = new StringBuffer();
      sb.append(x + ",");
      sb.append(y + ",");
      sb.append(step + ".");
      key = sb.toString();
    }
    if (map.containsKey(key)) {return map.get(key);}
    // calculate the probability of a state
    double probability = 0.0;
    if (x > 0) {probability += 0.25 * probabilityOfAlive(x - 1, y, n, step - 1, map);}
    if (x < (n - 1)) {probability += 0.25 * probabilityOfAlive(x + 1, y, n, step - 1, map);}
    if (y > 0) {probability += 0.25 * probabilityOfAlive(x, y - 1, n, step - 1, map);}
    if (y < (n - 1)) {probability += 0.25 * probabilityOfAlive(x, y + 1, n, step - 1, map);}
    // save the result to HashMap and return
    map.put(key, probability); return probability;
  }

  public static void main(String[] args)
  {
    System.out.println("probability1 = " + probabilityOfAlive(0, 0, 1));
    System.out.println("probability2 = " + probabilityOfAlive(0, 0, 2));
    System.out.println("probability3 = " + probabilityOfAlive(0, 0, 3));
  }
}