A 2D array of string is given to us. Each element is an array of two elements where first element is the prerequisite and the second element is a course. Print the first course the student should take and the final course. For example:
A->B
A->C
B->K
C ->K
L ->M
L ->N
D ->E
D ->J
E ->F
E ->G
F ->H
G ->I
Output;
A: K
L: M, N
D: H, I, J
Input given to us was a 2D array [[A,B],[A,C],[B,K],[C,K],[L,M],[L,N],[D,E],[D,J],[E,F],[E,G],[F,H],[G,I]]
public class Solution {
// If you need extra classes, you can define them privately here within class Solutionc
static class Pair{
int x, y;
public Pair(int x, int y){
this.x = x;
this.y = y;
}
public String toString(){
return x+" " + y;
}
}
static void findWord(String word, String[][] grid) {
for(int i=0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
findWordRecur(grid, i, j, 0, word, new ArrayList<>());
if(answer.size()!=0){
for(int k=0;k<answer.size()/2;k++){
System.out.println(answer.get(k));
}
return;
}
}
}
System.out.println("None");
}
static List<Pair> answer = new ArrayList<>();
static void findWordRecur(String [][] grid, int x, int y, int pointer, String word, List<Pair> path){
if(pointer==word.length()){
answer.addAll(path);
return;
}
if(x < 0 || x>= grid.length || y<0 || y >= grid[0].length){
return;
}
if(grid[x][y].equals(""+word.charAt(pointer))){
path.add(new Pair(x,y));
findWordRecur(grid, x+1, y, pointer+1, word, path);
findWordRecur(grid, x, y+1, pointer+1, word, path);
path.remove(path.size()-1);
}
}
// DO NOT MODIFY MAIN()
public static void main(String[] args) {
String arg0 = null;
List<String[]> arg1 = new ArrayList<String[]>();
String line;
boolean first_arg = true;
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
while ((line = br.readLine()) != null) {
if (line.equals("")) {
continue;
}
if(first_arg) {
arg0 = line;
first_arg = false;
} else {
arg1.add(line.split(" "));
}
}
} catch (IOException e) {
e.printStackTrace();
return;
}
String[][] grid = arg1.toArray(new String[arg1.size()][]);
findWord(arg0, grid);
}
}