Gold Mine Problem :

Rectangular grid of gold mine is given with R rows and C columns. Grid has R x C cells in it.
Each Cell is denoted by an integer , which is the count of gold content in that cell.

Sub rectangle is defined by four integers x1,y1,x2,y2 ,
where 1<=x1<=x2<=R and 1<=y1<=y2<=C.

Aim is to find the total gold in that given sub rectangle.

For Example:

Input Matrix is      
                             2 3 4 5
                             1 7 3 1
                             8 9 4 6
                             7 3 5 6

and  x1=1 , y1=1 , x2= 2 , y2 = 4  (yellow shaded region is the sub rectangle formed by these points).

Then , output should be sum of 2+3+4+5+1+7+3+1 = 26.

Algorithm:-

1. Input : array and two co-ordinates of rectangle say x1,y1 and x2,y2.
2. for i from x1-1 to x2-1 do
3. for j from y1-1 to y2-1 do
4. sum = sum+array[i][j]


Complexity:- O(n2)


Java implementation of algorithm

package problem.goldmine;

import java.util.Scanner;

public class GoldMine {

    public static void main(String[] args) {
       
        System.out.println("Enter row (M): ");  //Input rows
        Scanner scan = new Scanner(System.in);
        int row = Integer.parseInt(scan.nextLine());
       
        System.out.println("Enter column (N): ");  //Input columns
        Scanner scan1 = new Scanner(System.in);
        int column = Integer.parseInt(scan1.nextLine());
       
        int array[][] = new int[row][column];
       
        for(int r=0;r<row;r++){                       // Input binary matrix
            System.out.println("Enter row "+(r+1));
            for(int c=0;c<column;c++){
                Scanner scan2 = new Scanner(System.in);
                array[r][c]=Integer.parseInt(scan2.nextLine());
            }
        }
       
        System.out.println("Enter x1 : "); 
        Scanner scanx1 = new Scanner(System.in);
        int x1 = Integer.parseInt(scanx1.nextLine());
       
        System.out.println("Enter y1 : "); 
        Scanner scany1 = new Scanner(System.in);
        int y1 = Integer.parseInt(scany1.nextLine());
       
        System.out.println("Enter x2 : "); 
        Scanner scanx2 = new Scanner(System.in);
        int x2 = Integer.parseInt(scanx2.nextLine());
       
        System.out.println("Enter y2 : "); 
        Scanner scany2 = new Scanner(System.in);
        int y2 = Integer.parseInt(scany2.nextLine());
       
        System.out.println();
        display(array,row,column);
        System.out.println();
       
        int sum = 0;
        long startTime = System.currentTimeMillis();
        for(int i=x1-1;i<x2;i++){
            for(int j=y1-1;j<y2;j++){
                sum = sum + array[i][j];
            }
        }
        System.out.println("sum of gold mine in rectangle  formed by ("+x1+","+y1+") and ("+x2+","+y2+") ="+sum);
       
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Time Taken= "+(double)elapsedTime/1000+" sec");
       
       

    }
   
    static void display(int[][] array,int row,int column) {         //function to display matrix
        for(int r=0;r<row;r++){
            System.out.println();
            for(int c=0;c<column;c++){
                System.out.print(array[r][c]);
            }
        }
       
    }

}


Output:-

Enter row (M):
4
Enter column (N):
4
Enter row 1
2
8
9
7
Enter row 2
5
8
1
7
Enter row 3
5
7
3
5
Enter row 4
4
8
7
4
Enter x1 :
1
Enter y1 :
4
Enter x2 :
2
Enter y2 :
4


2897
5817
5735
4874
sum of gold mine in rectangle  formed by (1,4) and (2,4) =14
Time Taken= 0.0 sec