Problemas de Programação

Link to the problem: http://br.spoj.com/problems/COLOR11/ This problem wants us to find the amount of squares that a child can paint using only a color. One way of solving this problem is using Flood Fill, an algorithm that finds all the squares of the matrix that are connected to the initial square. The solution below is using a non-recursive implementation (Breath-First Search) to find the answer. import java.io.*; import java.util.*; class Main {     public int numRows;     public int numCols;     public int[][] matrix;     public boolean[][] visited;     public int count;     public int[] vi = {-1,-1,-1,0,0,1,1,1};     public int[] vj = {-1,0,1,-1,1,-1,0,1};         public void bfs(int currI, int currJ) {         Queue<Coord> queue = new ArrayDeque<Coord>();         queue.add(new Coord(currI, currJ));                 while (queue.size() > 0) {             Coord c = queue.poll();             int i = c.i;             int j = c.j;                         if (visite

Link to the problem: http://br.spoj.com/problems/PESCA11/ The solution below uses a matrix to keep the areas where a mesh is placed. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 int numMesh = Integer.parseInt(br.readLine());         int[][] sea = new int[101][101];         for (int i = 0; i < numMesh; i++) {             String line = br.readLine();             String[] s = line.split("\\s");             int xi = Integer.parseInt(s[0]);             int xf = Integer.parseInt(s[1]);             int yi = Integer.parseInt(s[2]);             int yf = Integer.parseInt(s[3]);             for (int j = xi; j < xf; j++) {                 for (int k = yi; k < yf; k++) {                     sea[j][k] = 1;                                }             }         }                 int count = 0;         for

Link to the problem: http://br.spoj.com/problems/GINCAN11/ If you want to see another solution for this problem, click here . This solution used Depth-First Search to solve this problem. Given a student, we call the DFS method in order to find all the students that are related to him/her. Then, a whole group of friends will be covered by each call to the DFS method, which give us the answer to this problem. import java.io.*; import java.util.*; class Main {     public HashMap<Integer, ArrayList<Integer>> adjList;     public boolean[] visited;         public void dfs(int currStudent) {         if (visited[currStudent]) {             return;         }                 visited[currStudent] = true;         ArrayList<Integer> friends = adjList.get(currStudent);         for (int i = 0; i < friends.size(); i++) {             dfs(friends.get(i));         }     }         public void process() throws NumberFormatException, IOException {         BufferedReader br = new

Link to the problem: http://br.spoj.com/problems/GINCAN11/ We need to find all the different teams that are possible to create. Each group of friends compose a team. Then, the solution below uses the Union-Find approach to separate each group of friends. In the end, it is only necessary to count how many connected components we have. import java.io.*; import java.util.*; class Main {     public int[] nodeParent;     public int[] depth;         public int count(int numStudents) {         int[] rootArray = new int[numStudents+1];         for (int i = 1; i <= numStudents; i++) {             rootArray[root(nodeParent[i])]++;         }                 int countDiffRoot = 0;         for (int i = 1; i <= numStudents; i++) {             if (rootArray[i] != 0) {                 countDiffRoot++;             }         }                 return countDiffRoot;     }         public int root(int n) {         while (nodeParent[n] != n) {             n = nodeParent[n];         }              

Link to the problem: http://br.spoj.com/problems/REUNIAO2/ If you want to see another solution for this problem, click here . The solution below calls the Dijkstra method for every city where the reunion could be taken. Then, it is possible to know what is going to be the maximum distance that a driver will have to drive if a specific city was chosen. Finally, we only need to find the minimum distance among these maximum distances, and we will have our answer for the problem. import java.io.*; import java.util.*; class Main {     public HashMap<Integer, ArrayList<Edge>> adjList;         public Comparator<Edge> costComparator = new Comparator<Edge>() {         public int compare(Edge e1, Edge e2) {             return e1.cost-e2.cost;         }     };         public int dijkstra(int end, int numCities) {         Queue<Edge> queue = new PriorityQueue<Edge>(numCities, costComparator);         queue.add(new Edge(end, 0));                 HashSet<

Link to the problem: http://br.spoj.com/problems/REUNIAO2/ The problem wants us to choose a city observing that the distance that the driver that will have to drive the maximum distance is the minimum. It means that we will need to calculate the distance between every pair of cities. The Floyd-Warshall algorithm calculates the shortest path between every pair of vertexes in a graph. Therefore, the solution below used this algorithm to find the answer. import java.io.*; import java.util.*; class Main {     public int[][] adjMatrix;         public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 String line = br.readLine();         String[] s = line.split("\\s");         int numCities = Integer.parseInt(s[0]);         int numRoads = Integer.parseInt(s[1]);                     adjMatrix = new int[numCities][numCities];         for (int i = 0; i < numCities; i++)

Link to the problem: http://br.spoj.com/problems/COPA14/ The problem wants us to find a path among the cities that results in a minimum cost. For this reason, the solution below used Prim's algorithm. P.S.: Remember that the railways have priority over the highways. import java.io.*; import java.util.*; class Main {     public HashMap<Integer, ArrayList<Edge>> adjList;         public Comparator<Edge> costComparator = new Comparator<Edge>() {         public int compare(Edge e1, Edge e2) {             if (e1.type-e2.type == 0) {                 return e1.cost-e2.cost;             }             return e1.type-e2.type;         }       };         public int prim(int start, int numCities) {         Queue<Edge> queue = new PriorityQueue<Edge>(numCities, costComparator);         queue.add(new Edge(start, 0, 0));                 HashSet<Integer> visited = new HashSet<>();                 int currTotalCost = 0;         while (queue.size(

Link to the problem: http://br.spoj.com/problems/TELEMAR7/ If you want to see another solution for this problem, click here . The solution below uses a PriorityQueue to keep the sellers and their calls. It provides the seller who has the shortest call. If more than a call has the same minimum value, it provides the seller whose id is the minimum. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 String line = br.readLine();         String[] s = line.split("\\s");         int numSellers = Integer.parseInt(s[0]);         int numCalls = Integer.parseInt(s[1]);                 Queue<Seller> queue = new PriorityQueue<Seller>(); // keep the time of the calls for each seller         for (int i = 0; i < numSellers; i++) {             queue.add(new Seller(i, 0));         }        

Link to the problem: http://br.spoj.com/problems/TELEMAR7/ The solution below tries to relate a call to each seller whenever the seller is available. If there is no seller available, the time of the calls is decreased until a seller becomes available, and until there is no more calls to be done. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);                 int numSellers = sc.nextInt();         int numCalls = sc.nextInt();         int numAvailableSellers = numSellers;         int[] sellers = new int[numSellers]; // keep the time of the current call         int[] sellersCalls = new int[numSellers]; // keep how many calls each seller did         for (int i = 0; i < numCalls; i++) {             for (int j = 0; j < numSellers; j++) { // relate a call to an available seller                 if (sellers[j] != 0) {                     continue;                 }   

Link to the problem:  https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=92 Every word is kept in a group that is featured by its amount of characters. Words that have the same amount of characters are in the same group. Then, the words that are unique in their groups compose the requested answer. import java.io.*; import java.util.*; class Main {     public HashMap<HashMap<Character, Integer>, ArrayList<String>> map;          public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  map = new HashMap<>();                  String line = br.readLine();         while (!line.equals("#")) {             String[] words = line.split("\\s");                          for (int i = 0; i < words.length; i++) {                 HashMap<Character, Intege

Link to the problem:  https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1039 The solution below used Backtracking to find all the permutation possible. import java.io.*; import java.util.*; class Main {     public int[] considered;     public String line;     public TreeSet<String> strings; // keep string sorted lexicographically          public void rec(StringBuilder sb) {         if (sb.length() == line.length()) {             strings.add(sb.toString());             return;         }                  for (int i = 0; i < line.length(); i++) {             if (considered[i] == 1) {                 continue;             }             considered[i] = 1;             sb.append(line.charAt(i));             rec(sb);             sb.deleteCharAt(sb.length()-1);             considered[i] = 0;         }     }          public void process() throws NumberFormatException, IOException {

Link to the problem:  https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2162 The solution below tries to find out if the entry is palindrome. Then, if this condition is fulfilled, it is checked it the sentence can be allocated in a matrix NxN. Finally, we check if the sentence can be read from the table in the given four different ways.  import java.io.*; import java.util.*; class Main {     public HashSet<Character> notValid;     public HashSet<String> string;     public char[][] matrix;          public void initSet() {         notValid.add('.');         notValid.add(' ');         notValid.add(',');         notValid.add('?');         notValid.add('!');         notValid.add('(');         notValid.add(')');     }          public void check(int start, int end, boolean lateral) {         StringBuilder sb = new StringBuilder()

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=342 The solution below keeps a map that associates a character with its mirror character, which we use to check if the entry is a mirrored string. Moreover, it is also checked if the entry is a regular palindrome. Then, the answer is given according to the fulfilled properties. import java.io.*; import java.util.*; class Main {     public HashMap<Character, Character> reverse;          public void initMap() {         reverse.put('A', 'A');         reverse.put('E', '3');         reverse.put('H', 'H');         reverse.put('I', 'I');         reverse.put('J', 'L');         reverse.put('L', 'J');         reverse.put('M', 'M');         reverse.put('O', 'O');         reverse.put('S', '2&