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 #

1. BFS(Breadth-First-Search),
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<Integer[]> list = new ArrayList<Integer[]>();
//
//  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<Position> queue = new LinkedList<Position>();
  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 + ")";
 }
 
 
}
-
Labels: ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)