Posts

(USACO) Your Ride Is Here - Solution

import java.io.*; import java.util.*; class ride {     public static String alphabet = "0ABCDEFGHIJKLMNOPQRSTUVWXYZ";         public static void main (String [] args) throws IOException {         BufferedReader f = new BufferedReader(new FileReader("ride.in"));                                                                                                             PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("ride.out")));              ...

(UVA) Knights in FEN - Solution

I solved this problem by a simple brute force. I used Depth-First Search-like algorithm to try all the moves. Then, I registered the optimal solution among all solutions that I found. import java.io.*; import java.util.*; class Main  {     public static int[][] m = new int[5][5];     public static int[][] model = {{1,1,1,1,1}, {0,1,1,1,1}, {0,0,2,1,1}, {0,0,0,0,1}, {0,0,0,0,0}};     public static int moves = 0;     public static int resultMoves = 1000000000;     public static int[] vi = {-2,-2,2,2,-1,-1,1,1};     public static int[] vj = {-1,1,-1,1,-2,2,-2,2};             public static boolean checkStatusBoard() {         for (int i = 0; i < 5; i++) {             for (int j = 0; j < 5; j++) {         ...

(UVA) The Seasonal War - Solution 3

This solution is using Depth-First Search. If you want to see other solutions for this problem, click here and here . Both of them are using Breadth-First Search. import java.io.*; import java.util.*; class Main  {     public static int[][] m;     public static int[][] visited;         public static void dfs(int squareDimension, int i, int j) {         if (i < 0 || j < 0 || i >= squareDimension || j >= squareDimension || visited[i][j] == 1 || m[i][j] == 0s) {           return;         }                 int[] vi = {-1,-1,-1,0,0,1,1,1};         int[] vj = {-1,0,1,-1,1,-1,0,1};                 visited[i][j] =...

(UVA) You want what filled? - Solution 2

For this solution, I used Breadth-First Search. If you want to see another solution using Depth-First Search, click here . import java.io.*; import java.util.*; class Main  {     public static char[][] m;     public static char[][] addedToQueue;     public static int count;         public static void bfs(int i, int j, int rows, int cols) {         Queue<Coord> queue = new ArrayDeque<Coord>();         Coord c = new Coord(i, j);         queue.add(c);         addedToQueue[i][j] = 1;                 int[] vi = {-1,1,0,0};         int[] vj = {0,0,-1,1};                 while (queue.size(...

(UVA) You want what filled? - Solution 1

I used Depth-First Search to solve this problem. import java.io.*; import java.util.*; class Main  {     public static char[][] m;     public static char[][] visited;     public static int count;         public static void dfs(char letter, int i, int j, int rows, int cols) {         int[] vi = {-1,1,0,0};         int[] vj = {0,0,-1,1};                 if (m[i][j] != letter) {             return;         }         else {             count++;             visited[i][j] = 1;             ...

(UVA) Dominos 2 - Solution 2

I used Breadth-First Search to solve this problem. If you want to see this problem solved using Depth-First Search, click here . Initially, I added all the dominos knocked over by hand in a Queue. Then, in the BFS method, for every domino already knocked I checked if it would make another domino to fall over. If yes, I added this domino to the Queue. Besides, every knocked domino was stored in a HashSet in order to do not have any domino considered more than once and to give the total number of dominos that fell over.  import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<Integer>> knocks = new HashMap<Integer, ArrayList<Integer>>();        public static int bfs(Queue<Integer> knockedDominos, HashSet<Integer> considered) {         while (knockedDominos.size() > 0) {         ...

(UVA) Dominos 2 - Solution 1

I used Depth-First Search to solve this problem. Initially, for every domino knocked by hand, I called the DFS method. Then, in this method, I checked if the current domino would make another one to fall over. If yes, I called the DFS method for every reachable node. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<Integer>> knocks = new HashMap<Integer, ArrayList<Integer>>();     public static int[] visited;         public static int dfs(int domino) {         int count = 0;                 if (visited[domino] == 0) {             visited[domino] = 1;             count++;            ...