アルゴリズム:馬が川を渡る

import java.util.HashMap;
import java.util.Map;

/**
 *   :  {M,N}       =   {M-1,N}     +   {M,N-1}    
 *     MAP,    {x,y}    ,          ,    
 * 
 * @author xiaojianhx
 * @date 2012-10-19
 */
public class Demo {

    /** X   */
    private int maxX;

    /** Y   */
    private int maxY;

    /**        */
    private int[] c_axis;

    /**             */
    private int[][] ma;

    /**           */
    private Map<String, Long> data = new HashMap<String, Long>();

    /**
     *     
     * 
     * @param b_axis
     *                  
     * @param c_axis
     *                  
     * @return Long             
     */
    public Long getResult(int[] b_axis, int[] c_axis) {

        //    
        init(b_axis, c_axis);

        return getCount(maxX, maxY);
    }

    /**
     *    
     * 
     * @param b_axis
     *                
     * @param c_axis
     *                  
     */
    private void init(int[] b_axis, int[] c_axis) {

        maxX = b_axis[0];
        maxY = b_axis[1];

        this.c_axis = c_axis;

        //               
        initMa();
    }

    /**
     *            
     */
    private void initMa() {

        ma = new int[maxX + 1][maxY + 1];

        for (int i = 0; i <= maxX; i++) {
            for (int j = 0; j <= maxY; j++) {
                if (isMa(i, j)) {
                    ma[i][j] = -1;
                } else {
                    ma[i][j] = 0;
                }
            }
        }
    }

    /**
     *       ,     
     * <li>           1 2</li>
     * <li>        </li>
     * 
     * @param x
     *            X  
     * @param y
     *            Y  
     * @return boolean       ,      TRUE:   ;FALSE:    
     */
    private boolean isMa(int x, int y) {

        int tmpX = Math.abs(x - c_axis[0]);
        int tmpY = Math.abs(y - c_axis[1]);

        if (tmpX == 1 && tmpY == 2) {
            return true;
        }

        if (tmpX == 2 && tmpY == 1) {
            return true;
        }

        return tmpX == 0 && tmpY == 0;
    }

    /**
     *     {x,y}    
     * 
     * @param x
     *            X  
     * @param y
     *            Y  
     * @return Long   {x,y}    
     */
    private Long getCount(int x, int y) {

        //     :  {x,y}    ,     ,  0,  
        if (check(x, y)) {
            return 0L;
        }

        //     :    ,  1
        if (x == 0 && y == 0) {
            return 1L;
        }

        // MAP     {x-1,y}    
        Long value0 = data.get((x - 1) + "," + y);

        // MAP     {x,y-1}    
        Long value1 = data.get(x + "," + (y - 1));

        //     ,       ,(           )
        value0 = getCount(x - 1, y, value0);
        value1 = getCount(x, y - 1, value1);

        //   {x,y}       =   {x-1,y}     +   {x,y-1}    ,    MAP,     
        Long c = value0 + value1;

        data.put(x + "," + y, c);

        return c;
    }

    /**
     *   Y  
     * 
     * @param x
     *            X  
     * @param y
     *            Y  
     * @param val
     *              {x,y}    
     * @return Long   {x,y}    
     */
    private Long getCount(int x, int y, Long val) {
        return val != null ? val : getCount(x, y);
    }

    /**
     *           
     * <li>{x,y}      </li>
     * <li>{x,y}   </li>
     * 
     * @param x
     *            X  
     * @param y
     *            Y  
     * @return boolean           TRUE: ;FALSE:  
     */
    private boolean check(int x, int y) {
        return x < 0 || y < 0 || ma[x][y] == -1;
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 30; i++) {
            long l0 = System.currentTimeMillis();
            int[] b_axis = { i, i };
            int[] c_axis = { 3, 2 };
            long count = new Demo().getResult(b_axis, c_axis);
            long l1 = System.currentTimeMillis();
            System.out.println("{" + i + "," + i + "}:  " + (l1 - l0) + "[MS],   " + count);
        }
    }
}

{1,1}:  15[MS],   0
{2,2}:  0[MS],   1
{3,3}:  0[MS],   1
{4,4}:  0[MS],   0
{5,5}:  0[MS],   3
{6,6}:  0[MS],   17
{7,7}:  0[MS],   79
{8,8}:  0[MS],   341
{9,9}:  0[MS],   1420
{10,10}:  0[MS],   5797
{11,11}:  0[MS],   23387
{12,12}:  0[MS],   93652
{13,13}:  16[MS],   373218
{14,14}:  0[MS],   1482570
{15,15}:  0[MS],   5876662
{16,16}:  0[MS],   23260199
{17,17}:  0[MS],   91975390
{18,18}:  0[MS],   363455085
{19,19}:  0[MS],   1435667475
{20,20}:  0[MS],   5669633400
{21,21}:  0[MS],   22387608210
{22,22}:  0[MS],   88399757790
{23,23}:  16[MS],   349070903010
{24,24}:  0[MS],   1378530151050
{25,25}:  0[MS],   5444701787616
{26,26}:  0[MS],   21507902567778
{27,27}:  0[MS],   84975924943774
{28,28}:  0[MS],   335794021531576
{29,29}:  0[MS],   1327188954058100
{30,30}:  0[MS],   5246593689252916