Problemas de Programação

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=669&page=show_problem&problem=2391 For this problem, we need to find out if the graph is bipartite. The solution below used a Breath-First Search (BFS) to accomplish this task. import java.io.*; import java.util.*; class Main {        public ArrayList<ArrayList<Integer>> adjList;     public int[] nodes;         public boolean bfs(int start, int numNodes) {         Queue<Integer> queue = new ArrayDeque<>();         queue.add(start);         nodes[start] = 0;                 while (queue.size() > 0) {             int currNode = queue.poll();...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=669&page=show_problem&problem=945 For this problem, we need to find out if the graph is bipartite. The solution below used a Breath-First Search (BFS) to accomplish this task. import java.io.*; import java.util.*; class Main {        public ArrayList<ArrayList<Integer>> adjList;     public int[] nodesID;         public boolean bfs(int start, int numNodes) {         Queue<Integer> queue = new ArrayDeque<>();         queue.add(start);         nodesID[start] = 0;                 while (queue.size() > 0) {             int currNode = queue.poll();...

Link to the problem: http://br.spoj.com/problems/SETA14/ The solution below uses a Depth-First Search to solve this problem. In this method, every position that is valid is replaced by the character '*', and every position that is considered invalid is replaced by '#'. In the end, we only need to count how many '*' we have in our matrix. import java.io.*; import java.util.*; class solucao {     public HashMap<Character, Integer> map;     public char[][] matrix;     public boolean[][] visited;     public int size;     public int[] vi = {-1,0,0,1};     public int[] vj = {0,-1,1,0};         public char dfs(int currI, int currJ) {         if (currI < 0 || currJ < 0 || currI >= size || currJ >= size  || matrix[currI][currJ] == '#') {             return '#'; ...

Link to the problem: http://br.spoj.com/problems/LAB07/ The solution below uses the Breadth-First Search algorithm to find the answer to this problem. Every time, we have the choice of moving or staying in the same position.   import java.io.*; import java.util.*; class solucao {     public int[][] matrix;     public boolean[][] visited;     public int[] vi = {-1,0,0,1};     public int[] vj = {0,-1,1,0};     public int numRows;     public int numCols;         public int[][] updateMatrix(int[][] matrix) {         int[][] matrixTmp = new int[numRows][numCols];         for (int i = 0; i < numRows; i++) {             for (int j = 0; j < numCols; j++) {              ...

Link to the problem: http://br.spoj.com/problems/MATRIZ2/ The solution below multiplies matrix A and matrix B in order to get only the answer for the required position. There is no need to calculate all the positions of matrix C. import java.io.*; import java.util.*; class solucao {     public static int reader(BufferedReader br) throws NumberFormatException, IOException {              int n;         int resp = 0;                     while (true) {                      n = br.read();                      if (n >= '0' && n <= '9') {        ...

Link to the problem: http://br.spoj.com/problems/FUROS/ The solution below calculates the distance between every pair of holes. For every distance calculated, we keep the maximum distance. Then, we keep the minimum distance among the maximum distances. import java.io.*; import java.util.*; class solucao {     public static int reader(BufferedReader br) throws NumberFormatException, IOException {              int n;         int resp = 0;              int sinal = 1;                     while (true) {                      n = br.read();                 ...

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1557 The solution below used the concept of Knapsack, related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public int[] numbers;     public long[][][] matrix;     public int div;     public int maxNumbers;         public long knapsack(int sum, int indexNumbers, int numConsideredNumbers) {         if (numConsideredNumbers == maxNumbers) {             if (sum == 0) {                 return 1;             }             return 0;...