Editorial for Find Brian's Bitcoin!
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors:
The main idea for this problem is to do two times DFS or BFS, once from the starting position and once from the position of the Bitcoin. The solution is commented on throughout if something is not clear.
import java.util.Arrays;
import java.util.Scanner;
public class briansbitcoin {
static int startI, startJ, btcI, btcJ, ethI, ethJ, r, c; // Keep track of the location of the starting position, btc, and eth.
static void dfs(boolean[][] visit, char[][] grid, int curRow, int curCol) {
if (curRow < 0 || curCol < 0 || curRow >= r || curCol >= c || grid[curRow][curCol] == '#' || visit[curRow][curCol]) // If any of these conditions are true, the movement is not valid.
return;
visit[curRow][curCol] = true;
dfs(visit, grid, curRow + 1, curCol); // Go right
dfs(visit, grid, curRow - 1, curCol); //Go left
dfs(visit, grid, curRow, curCol + 1); //Go down
dfs(visit, grid, curRow, curCol - 1); // Go up
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
r = sc.nextInt(); c = sc.nextInt();
boolean[][] visited = new boolean[r][c]; // Keep tracking of all visited positions
char[][] grid = new char[r][c];
for (int i = 0; i < r; i++) {
String str = sc.next();
for (int j = 0; j < c; j++) {
grid[i][j] = str.charAt(j);
if (grid[i][j] == 's') {
startI = i;
startJ = j;
}
if (grid[i][j] == 'b') {
btcI = i;
btcJ = j;
}
if (grid[i][j] == 'e') {
ethI = i;
ethJ = j;
}
}
}
dfs(visited, grid, startI, startJ);
if (!visited[btcI][btcJ]) { // Checks if you can NOT reach the Bitcoin.
System.out.println("No Crypto For Brian!");
System.exit(0);
}
for (boolean[] row : visited) // Reset the visited grid in order for it to work during the second traversal.
Arrays.fill(row, false);
dfs(visited,grid,btcI,btcJ);
if(!visited[ethI][ethJ]) { // Checks if you can NOT reach the Ethereum.
System.out.println("No Crypto For Brian!");
System.exit(0);
}
System.out.println("Crypto For Brian"); // If both traversals are valid, then Brian can reach his crypto!
}
}
Comments