-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathExhaustiveSearch.java
More file actions
185 lines (158 loc) · 5.26 KB
/
ExhaustiveSearch.java
File metadata and controls
185 lines (158 loc) · 5.26 KB
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
import java.util.Scanner;
public class ExhaustiveSearch {
static LinkedListStack efficientPath = new LinkedListStack();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int row = scanner.nextInt();
int column = scanner.nextInt();
if ((row > 27) || (column > 27)) {
System.out.println("Map cannot be process");
return;
}
scanner.nextLine();
String[][] matrix = new String[row][column];
for (int i = 0; i < row; i++) {
String line = scanner.nextLine();
// check if the row has more colums than the input colums
String[] lines = line.split(" ");
if (lines.length > column) {
System.out.println("Map cannot be processes");
return;
}
// get each element in the column
for (int j = 0; j < column; j++) {
matrix[i][j] = lines[j];
}
}
// check if the app has more rows than the input row => break the program
if (scanner.hasNextLine()) {
System.out.println("Map cannot be process");
return;
}
// create a stack to store the path
LinkedListStack list = new LinkedListStack();
// generation method
generatePossiblePath(list, matrix, 0, 0);
// print the result
System.out.println("Step: " + list.minStep + "\nGold: " + list.maxGold);
System.out.println("Path: " + reverseString(list.path)); // the stack store the node backward so we need to reverse it to get the correct one
}
// reverse method
public static String reverseString(String inputString) {
String outString = "";
for (int i = inputString.length() - 1; i >= 0; i--) {
outString += inputString.charAt(i);
}
return outString;
}
public static void generatePossiblePath(LinkedListStack list, String[][]matrix, int row, int column) {
// check if the current position is out of map => break
if ((row >= matrix.length) || (column >= matrix[0].length)) {
return;
}
// if the current node is X => not process this way
if (matrix[row][column].equals("X")) {
return;
}
// if the current node is not . => note the gold value and process the right and bottom side recuresively
int gold = (!matrix[row][column].equals(".")) ? Integer.parseInt(matrix[row][column]) : 0;
// update new node to the stack
list.push(new State(row, column, gold));
// process the right and bottom way
generatePossiblePath(list, matrix, row, column + 1);
generatePossiblePath(list, matrix, row + 1, column);
// delete that node when finished
list.pop();
}
}
// the state describe the node information: gold value, row, column
class State {
int row;
int column;
int gold;
public State(int row, int column, int gold) {
this.column = column;
this.row = row;
this.gold = gold;
}
}
// create a custom stack
class LinkedListStack {
static class Node {
State data;
Node next;
public Node(State data) {
this.data = data;
this.next = null;
}
}
Node head;
int size;
// totalGold store the current gold value
int totalGold;
// maxGold save the current max gold value
int maxGold;
// minStep store the current minimum step
int minStep;
// store the efficiency path
String path;
public boolean isEmpty() {
return this.size == 0;
}
public LinkedListStack() {
this.head = null;
this.size = 0;
this.totalGold = 0;
this.maxGold = 0;
this.minStep = 0;
this.path = "";
}
public void push(State data) {
Node newNode = new Node(data);
if (this.size == 0) {
this.head = newNode;
this.size++;
this.totalGold += data.gold;
return;
}
this.totalGold += data.gold;
newNode.next = this.head;
this.head = newNode;
this.size++;
// when new node has been added => check the current total gold if it is greater than the current max gold => update maxGold, minSteps and path
if (totalGold > maxGold) {
maxGold = totalGold;
minStep = this.size - 1;
updatePath();
}
}
private void updatePath() {
Node current = this.head;
// traverse from head to the current node
this.path = "";
while (current.next != null) {
// if 2 node is at the same column => moving down
// otherwise, moving right
if (current.data.column - current.next.data.column == 0) {
path += "D";
}else {
path += "R";
}
current = current.next;
}
}
public State peek() {
if (this.size == 0) {
return null;
}
return this.head.data;
}
public void pop() {
if (this.size == 0) {
return;
}
this.totalGold -= this.head.data.gold;
this.head = this.head.next;
this.size--;
}
}