## Tuesday, March 10, 2015

### Project euler 81~ 83 : BFS(Breadth-First-Search)

These questions were very easy to me~!

Because I studied graph algorithm very hard and posted on my blogger.

https://projecteuler.net/problem=83

# List #

2. DFS(Depth-First-Search),
3. Prim algorithm,
4. Union Find algorithm,
5. Kruskal algorithm,
6. Topology algorithm,
7. dijkstra's algorithm

What I had to do was thinking about how to efficiently access good solution by past times.

I choosed BFS login with Queue and find all possible path.

condition
up case : if (sum[po.y - 1][po.x] > curSum + val[po.y - 1][po.x]) {
sum[po.y - 1][po.x] = curSum + val[po.y - 1][po.x];
queue.add(new Position(po.x, po.y - 1));
}

right down, left ...

[P (y=0 , x=0)]
[131, max, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]

[P (y=0 , x=1), P (y=1 , x=0)]
[131, 804, max, max, max]
[332, max, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]

[P (y=1 , x=0), P (y=0 , x=2), P (y=1 , x=1)]
[131, 804, 1038, max, max]
[332, 900, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]

[P (y=0 , x=2), P (y=1 , x=1), P (y=1 , x=1), P (y=2 , x=0)]
[131, 804, 1038, max, max]
[332, 428, max, max, max]
[962, max, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]

[P (y=1 , x=1), P (y=1 , x=1), P (y=2 , x=0), P (y=0 , x=3), P (y=1 , x=2)]
[131, 804, 1038, 1141, max]
[332, 428, 1380, max, max]
[962, max, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]

[P (y=1 , x=1), P (y=2 , x=0), P (y=0 , x=3), P (y=1 , x=2), P (y=1 , x=2), P (y=2 , x=1)]
[131, 804, 1038, 1141, max]
[332, 428, 770, max, max]
[962, 1231, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]

[P (y=2 , x=0), P (y=0 , x=3), P (y=1 , x=2), P (y=1 , x=2), P (y=2 , x=1)]
[131, 804, 1038, 1141, max]
[332, 428, 770, max, max]
[962, 1231, max, max, max]
[max, max, max, max, max]
[max, max, max, max, max]

[P (y=0 , x=3), P (y=1 , x=2), P (y=1 , x=2), P (y=2 , x=1), P (y=3 , x=0)]
[131, 804, 1038, 1141, max]
[332, 428, 770, max, max]
[962, 1231, max, max, max]
[1499, max, max, max, max]
[max, max, max, max, max]

[P (y=1 , x=2), P (y=1 , x=2), P (y=2 , x=1), P (y=3 , x=0), P (y=0 , x=4), P (y=1 , x=3)]
[131, 804, 1038, 1141, 1159]
[332, 428, 770, 2106, max]
[962, 1231, max, max, max]
[1499, max, max, max, max]
[max, max, max, max, max]

[P (y=1 , x=2), P (y=2 , x=1), P (y=3 , x=0), P (y=0 , x=4), P (y=1 , x=3), P (y=0 , x=2), P (y=1 , x=3), P (y=2 , x=2)]
[131, 804, 1004, 1141, 1159]
[332, 428, 770, 1735, max]
[962, 1231, 1516, max, max]
[1499, max, max, max, max]
[max, max, max, max, max]

[P (y=2 , x=1), P (y=3 , x=0), P (y=0 , x=4), P (y=1 , x=3), P (y=0 , x=2), P (y=1 , x=3), P (y=2 , x=2)]
[131, 804, 1004, 1141, 1159]
[332, 428, 770, 1735, max]
[962, 1231, 1516, max, max]
[1499, max, max, max, max]
[max, max, max, max, max]

[P (y=3 , x=0), P (y=0 , x=4), P (y=1 , x=3), P (y=0 , x=2), P (y=1 , x=3), P (y=2 , x=2), P (y=3 , x=1)]
[131, 804, 1004, 1141, 1159]
[332, 428, 770, 1735, max]
[962, 1231, 1516, max, max]
[1499, 1930, max, max, max]
[max, max, max, max, max]

[P (y=0 , x=4), P (y=1 , x=3), P (y=0 , x=2), P (y=1 , x=3), P (y=2 , x=2), P (y=3 , x=1), P (y=4 , x=0)]
[131, 804, 1004, 1141, 1159]
[332, 428, 770, 1735, max]
[962, 1231, 1516, max, max]
[1499, 1930, max, max, max]
[2304, max, max, max, max]

[P (y=1 , x=3), P (y=0 , x=2), P (y=1 , x=3), P (y=2 , x=2), P (y=3 , x=1), P (y=4 , x=0), P (y=1 , x=4)]
[131, 804, 1004, 1141, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, max, max]
[1499, 1930, max, max, max]
[2304, max, max, max, max]

[P (y=0 , x=2), P (y=1 , x=3), P (y=2 , x=2), P (y=3 , x=1), P (y=4 , x=0), P (y=1 , x=4), P (y=2 , x=3)]
[131, 804, 1004, 1141, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 2157, max]
[1499, 1930, max, max, max]
[2304, max, max, max, max]

[P (y=1 , x=3), P (y=2 , x=2), P (y=3 , x=1), P (y=4 , x=0), P (y=1 , x=4), P (y=2 , x=3), P (y=0 , x=3)]
[131, 804, 1004, 1107, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 2157, max]
[1499, 1930, max, max, max]
[2304, max, max, max, max]

[P (y=2 , x=2), P (y=3 , x=1), P (y=4 , x=0), P (y=1 , x=4), P (y=2 , x=3), P (y=0 , x=3)]
[131, 804, 1004, 1107, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 2157, max]
[1499, 1930, max, max, max]
[2304, max, max, max, max]

[P (y=3 , x=1), P (y=4 , x=0), P (y=1 , x=4), P (y=2 , x=3), P (y=0 , x=3), P (y=2 , x=3), P (y=3 , x=2)]
[131, 804, 1004, 1107, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, max]
[1499, 1930, 2013, max, max]
[2304, max, max, max, max]

[P (y=4 , x=0), P (y=1 , x=4), P (y=2 , x=3), P (y=0 , x=3), P (y=2 , x=3), P (y=3 , x=2), P (y=4 , x=1)]
[131, 804, 1004, 1107, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, max]
[1499, 1930, 2013, max, max]
[2304, 2662, max, max, max]

[P (y=1 , x=4), P (y=2 , x=3), P (y=0 , x=3), P (y=2 , x=3), P (y=3 , x=2), P (y=4 , x=1)]
[131, 804, 1004, 1107, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, max]
[1499, 1930, 2013, max, max]
[2304, 2662, max, max, max]

[P (y=2 , x=3), P (y=0 , x=3), P (y=2 , x=3), P (y=3 , x=2), P (y=4 , x=1), P (y=2 , x=4)]
[131, 804, 1004, 1107, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, 1420]
[1499, 1930, 2013, max, max]
[2304, 2662, max, max, max]

[P (y=0 , x=3), P (y=2 , x=3), P (y=3 , x=2), P (y=4 , x=1), P (y=2 , x=4), P (y=3 , x=3)]
[131, 804, 1004, 1107, 1159]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, 1420]
[1499, 1930, 2013, 2059, max]
[2304, 2662, max, max, max]

[P (y=2 , x=3), P (y=3 , x=2), P (y=4 , x=1), P (y=2 , x=4), P (y=3 , x=3), P (y=0 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, 1420]
[1499, 1930, 2013, 2059, max]
[2304, 2662, max, max, max]

[P (y=3 , x=2), P (y=4 , x=1), P (y=2 , x=4), P (y=3 , x=3), P (y=0 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, 1420]
[1499, 1930, 2013, 2059, max]
[2304, 2662, max, max, max]

[P (y=4 , x=1), P (y=2 , x=4), P (y=3 , x=3), P (y=0 , x=4), P (y=4 , x=2)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, 1420]
[1499, 1930, 2013, 2059, max]
[2304, 2662, 2537, max, max]

[P (y=2 , x=4), P (y=3 , x=3), P (y=0 , x=4), P (y=4 , x=2)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1938, 1420]
[1499, 1930, 2013, 2059, max]
[2304, 2662, 2537, max, max]

[P (y=3 , x=3), P (y=0 , x=4), P (y=4 , x=2), P (y=2 , x=3), P (y=3 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1842, 1420]
[1499, 1930, 2013, 2059, 2376]
[2304, 2662, 2537, max, max]

[P (y=0 , x=4), P (y=4 , x=2), P (y=2 , x=3), P (y=3 , x=4), P (y=4 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1309]
[962, 1231, 1516, 1842, 1420]
[1499, 1930, 2013, 2059, 2376]
[2304, 2662, 2537, 2096, max]

[P (y=4 , x=2), P (y=2 , x=3), P (y=3 , x=4), P (y=4 , x=3), P (y=1 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1420]
[1499, 1930, 2013, 2059, 2376]
[2304, 2662, 2537, 2096, max]

[P (y=2 , x=3), P (y=3 , x=4), P (y=4 , x=3), P (y=1 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1420]
[1499, 1930, 2013, 2059, 2376]
[2304, 2662, 2537, 2096, max]

[P (y=3 , x=4), P (y=4 , x=3), P (y=1 , x=4), P (y=3 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1420]
[1499, 1930, 2013, 1963, 2376]
[2304, 2662, 2537, 2096, max]

[P (y=4 , x=3), P (y=1 , x=4), P (y=3 , x=3), P (y=4 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1420]
[1499, 1930, 2013, 1963, 2376]
[2304, 2662, 2537, 2096, 2707]

[P (y=1 , x=4), P (y=3 , x=3), P (y=4 , x=4), P (y=4 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1420]
[1499, 1930, 2013, 1963, 2376]
[2304, 2662, 2537, 2096, 2427]

[P (y=3 , x=3), P (y=4 , x=4), P (y=4 , x=4), P (y=2 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1386]
[1499, 1930, 2013, 1963, 2376]
[2304, 2662, 2537, 2096, 2427]

[P (y=4 , x=4), P (y=4 , x=4), P (y=2 , x=4), P (y=4 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1386]
[1499, 1930, 2013, 1963, 2376]
[2304, 2662, 2537, 2000, 2427]

[P (y=4 , x=4), P (y=2 , x=4), P (y=4 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1386]
[1499, 1930, 2013, 1963, 2376]
[2304, 2662, 2537, 2000, 2427]

[P (y=2 , x=4), P (y=4 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1842, 1386]
[1499, 1930, 2013, 1963, 2376]
[2304, 2662, 2537, 2000, 2427]

[P (y=4 , x=3), P (y=2 , x=3), P (y=3 , x=4)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1963, 2342]
[2304, 2662, 2537, 2000, 2427]

[P (y=2 , x=3), P (y=3 , x=4), P (y=4 , x=4), P (y=4 , x=2)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1963, 2342]
[2304, 2662, 2524, 2000, 2331]

[P (y=3 , x=4), P (y=4 , x=4), P (y=4 , x=2), P (y=3 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1929, 2342]
[2304, 2662, 2524, 2000, 2331]

[P (y=4 , x=4), P (y=4 , x=2), P (y=3 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1929, 2342]
[2304, 2662, 2524, 2000, 2331]

[P (y=4 , x=2), P (y=3 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1929, 2342]
[2304, 2662, 2524, 2000, 2331]

[P (y=3 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1929, 2342]
[2304, 2662, 2524, 2000, 2331]

[P (y=4 , x=3)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1929, 2342]
[2304, 2662, 2524, 1966, 2331]

[P (y=4 , x=4), P (y=4 , x=2)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1929, 2342]
[2304, 2662, 2490, 1966, 2297]

[P (y=4 , x=2)]
[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1929, 2342]
[2304, 2662, 2490, 1966, 2297]

[131, 804, 1004, 1107, 1125]
[332, 428, 770, 1735, 1275]
[962, 1231, 1516, 1808, 1386]
[1499, 1930, 2013, 1929, 2342]
[2304, 2662, 2490, 1966, 2297]

and my source is

below

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159``` ```package euler.numberFrom71; import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class number83 { public static void main(String args[]) throws FileNotFoundException { long start = System.currentTimeMillis(); // Scanner scan = new Scanner( // new File( // "D:/app/tool/eclipse-kepler-server/workspace/euler/src/euler/p081_matrix.txt")); // // int total = 0; // String read = ""; // // ArrayList list = new ArrayList(); // // while (scan.hasNextLine()) { // String str = scan.nextLine(); // String[] strNum = str.split(","); // Integer nums[] = new Integer[strNum.length]; // for (int i = 0; i < strNum.length; i++) { // nums[i] = Integer.parseInt(strNum[i]); // } // // list.add(nums); // } // // Integer val[][] = new Integer[list.size()][list.get(0).length]; // // for (int i = 0; i < list.size(); i++) { // val[i] = list.get(i); // } int [][] val = new int[][] { {131,673,234,103,18}, {201,96,342,965,150}, {630,803,746,422,111}, {537,699,497,121,956}, {805,732,524,37,331} }; long[][] sum = new long[val.length][val[0].length]; String[][] path = new String[val.length][val[0].length]; long min = Long.MAX_VALUE; for (int k = 0; k < path.length; k++) { for (int j = 0; j < path.length; j++) { Arrays.fill(sum[k], Integer.MAX_VALUE); } } sum[0][0] = val[0][0]; Queue queue = new LinkedList(); Position position = new Position(0, 0); queue.add(position); while (!queue.isEmpty()) { System.out.println(queue); Position po = queue.poll(); long curSum = sum[po.y][po.x]; // up for (int j = 0; j < path.length; j++) { System.out.println(Arrays.toString(sum[j])); } System.out.println(); if (canGo(po.x, po.y - 1)) { if (sum[po.y - 1][po.x] > curSum + val[po.y - 1][po.x]) { sum[po.y - 1][po.x] = curSum + val[po.y - 1][po.x]; queue.add(new Position(po.x, po.y - 1)); } } // right if (canGo(po.x + 1, po.y)) { if (sum[po.y][po.x + 1] > curSum + val[po.y][po.x + 1]) { sum[po.y][po.x + 1] = curSum + val[po.y][po.x + 1]; queue.add(new Position(po.x + 1, po.y)); } } // left if (canGo(po.x - 1, po.y)) { if (sum[po.y][po.x - 1] > curSum + val[po.y][po.x - 1]) { sum[po.y][po.x - 1] = curSum + val[po.y][po.x - 1]; queue.add(new Position(po.x - 1, po.y)); } } // down if (canGo(po.x, po.y + 1)) { if (sum[po.y + 1][po.x] > curSum + val[po.y + 1][po.x]) { sum[po.y + 1][po.x] = curSum + val[po.y + 1][po.x]; queue.add(new Position(po.x, po.y + 1)); } } } for (int j = 0; j < path.length; j++) { System.out.println(Arrays.toString(sum[j])); } for (int j = 0; j < path.length; j++) { min = Math.min(min, sum[j][4]); } System.out.println(sum[4][4]); System.out.println(System.currentTimeMillis() - start); } public static boolean canGo(int x, int y) { int limit = 5; if (0 <= x && x < limit && 0 <= y && y < limit) { return true; } return false; } } class Position { int x; int y; public Position(int x, int y) { this.x = x; this.y = y; } /* (non-Javadoc) * @see java.lang.Object#toString() */ @Override public String toString() { return "P (y=" + y + " , x=" + x + ")"; } } ```