(UVA) Square Sums - Solution

I used Depth-First Search to solve this problem.


import java.io.*;
import java.util.*;
import java.lang.Math;

class Main  {
    public static int[][] matrix;
    public static boolean[][] visited;
    public static int count;
    public static int dimension;
    public static int[] vi = {-1,0,0,1};
    public static int[] vj = {0,-1,1,0};
   
    public static void dfs(int currI, int currJ, int border) {
        //if (currI < 0 || currJ < 0 || currI >= dimension || currJ >= dimension || (currI != border && currJ != border && currI != dimension-border-1 && currJ != dimension-border-1) || visited[currI][currJ]) {
        if (currI < 0 || currJ < 0 || currI >= dimension || currJ >= dimension || (currI != border && currJ != border) || visited[currI][currJ]) {
            return;
        }
       
        visited[currI][currJ] = true;
        count += matrix[currI][currJ];
        for (int i = 0; i < 4; i++) {
            int nextI = currI+vi[i];
            int nextJ = currJ+vj[i];
            dfs(nextI, nextJ, border);
        }
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCase = 0;
       
        dimension = reader(br);
        while (dimension != 0) {
            matrix = new int[dimension][dimension];
           
            for (int i = 0; i < dimension; i++) {
                for (int j = 0; j < dimension; j++) {
                    matrix[i][j] = reader(br);
                }
            }
           
            int qty = (int)Math.ceil((double)dimension/2);
            int[] sums = new int[qty];
           
            visited = new boolean[dimension][dimension];
            for (int i = 0; i < qty; i++) {
                count = 0;
                dfs(i, i, i);
                dfs(dimension-i-1, dimension-i-1, dimension-i-1);
                sums[i] = count;
            }
                       
            System.out.print("Case " + ++numCase + ": ");
            for (int i = 0; i < qty-1; i++) {
                System.out.print(sums[i] + " ");           
            }
            System.out.println(sums[qty-1]);
           
            dimension = reader(br);
        }
               
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução