Problem15

1.package com.yao.Algorithms;  
2.  
3.import java.util.HashMap;  
4.import java.util.Map;  
5./** 
6. *  
7. * @author shuimuqinghua77 @date 2011-11-29 
8. * 
9. */  
10.public class Problem15 {  
11.    private static Map<String, Node> seed = new HashMap<String, Node>();  
12.    private static int SIZE = 20;  
13.    private static long sum = 0;  
14.  
15.    public static void main(String[] args) {  
16.        seed.put(0 + ":" + 0, new Node(0, 0, 1));  
17.        for (int i = 0; i < SIZE + SIZE; i++) {  
18.            Map<String, Node> map = new HashMap<String, Node>();  
19.            for (Node node : seed.values()) {  
20.                if (node.x == SIZE || node.y == SIZE) {  
21.                    sum += node.size;  
22.                    continue;  
23.                }  
24.                search(node.x + 1, node.y, node.size, map);  
25.                search(node.x, node.y + 1, node.size, map);  
26.            }  
27.            seed = map;  
28.        }  
29.        System.out.println(sum);  
30.    }  
31.  
32.    private static void search(int x, int y, long size, Map<String, Node> map) {  
33.        Node node = new Node(x, y, size);  
34.        String key = x + ":" + y;  
35.        if (map.get(key) != null)  
36.            map.get(key).size += size;  
37.        else  
38.            map.put(key, node);  
39.    }  
40.}  
41.  
42.class Node {  
43.    int x;  
44.    int y;  
45.    long size;  
46.  
47.    public Node(int x, int y, long size) {  
48.        this.x = x;  
49.        this.y = y;  
50.        this.size = size;  
51.    }  
52.}