Assignment 3 Solution

Rules

    1. There are six questions in this assignment. You can get full mark 100 points by finished part of the questions, and the total score of this assignment will be no more than 100 points.

    2. Please submit “.java” file of these questions.

    3. The class name of each “.java” file should be A3Q1, A3Q2, A3Q3, A3Q4, A3Q5, and A3Q6 respectively to represent these six questions.
    4. No Chinese characters are allowed to appear in your code.

    5. No package included.

    6. The arguments and the output must strictly follow the description and the sample of each question. In this assignment, you can only use Scanner to get input.
    7. Please submit your assignment on the SAKAI site of your lab section. Marks will be deducted if you submit later than the deadline. If you submit your assignment within 24 hours after the deadline (grace period), your score will be half of the score you could get if the submission was made before the deadline. Assignments submitted after the grace period will not be graded (meaning you will get a zero for the assignment).

A3Q1: Greatest Common Divisor (GCD) [25 points]

Given an m*n matrix (0<m<10^5, 0<n<10^5), and the elements of the matrix are all positive integers. Write a program to calculate and output n GCDs of all elements of n columns in the matrix.

Input:

The first line of input is an integer s representing the number of matrices (0<s<100), followed by s matrixes. Each matrix input form is: The first line is the matrix's m and n, followed by the m-line input, with n elements in each line.
Output:

Please output the n GCDs of each matrix in order by line.


Sample:


A3Q2: Water Storage [25 points]

Given a one-dimensional array containing n positive integers (0<n<100), the number of the array represents the height of the column, and the depressed portion between the columns can store water. As the figure shown below, you can store 6 units of water. Write a program to calculate how many units of water an array can store.




Input:

The first line of input is an integer n representing the length of the array. The second line is n integers which are the elements of the array.
Output:

How many units of water the array can store.


Sample:


A3Q3: Spiral Matrix [25 points]

Given two integers m, n (0<m<10, 0<n<10), generate a m*n matrix filled with elements from 1 to m*n in anticlockwise spiral order, starting from the top right corner.

Input:

The input is two integers m, n.


Output:

Please output the m*n spiral matrix as the sample.


Sample:


A3Q4: Sum of Sub-matrix [25 points]

Given an integer matrix of m*n (0<m<100, 0<n<100), and T queries. Each query includes two sets of coordinates: the upper left coordinate (x1, y1) and the lower right coordinate (x2 , y2 ) (x1 <= x2, y1 <= y2). Please write a program to calculate the sum of all the integers in the sub-matrix determined by each set of coordinates.
As shown in the figure below, the coordinates (2, 1) (3, 3) determine the red sub-matrix. The sum of all the elements in this sub-matrix is 93








Input:

The first line of input is two integers m, n, followed by m lines with n integers which represents the elements of the matrix. Then, there will be T lines of queries, and each line includes four integers x1, y1, x2, y2.
Output:

Please output T lines of result of the queries in order.


Sample:


A3Q5: The Biggest Island [50 points]

Given a matrix of m*n (0<m<100, 0<n<100). The matrix contains only 0 and 1, where 0 represents the sea and 1 represents the land. Assuming that the outside of the matrix is all sea, please write a program to calculate the area of the largest island (i.e. how many 1s are included).

Input:

The first line of input is two integers m, n, followed by m lines with n 0/1s which represents the elements of the matrix.
Output:

Please output the area of the largest island. As shown in the figure below, area of the biggest island is 8.











Sample:


A3Q6: Shortest Path [50 points]

Given an integer matrix of m*n (0<m<10, 0<n<10). You need to go from the top left corner of the matrix to the bottom right corner, and you can only go right or down. The value of each point is the distance you need to complete if you go through this point. Write a program to find the shortest path and output the total distance of this path.

Input:

The first line of input is two integers m, n, followed by m lines with n integers which represents the elements of the matrix.
Output:

Please output the length of the shortest path.


Sample: