7623. Lucky chances

Lucky Chances is a lottery game. Each lottery ticket has a play field and a scratch area. The play field is a rectangular r × c field filled with numbers. The scratch area hides row and column numbers that specify the bet cell.

There are four possible winning directions: up, down, left and right. You win a direction if all numbers in this direction from the bet cell are strictly less than a number in the bet cell. And if the bet cell is on the edge of the grid, you win the corresponding direction automatically!

Larry wants to choose the ticket that has maximum total number of winning directions for all possible bet cells. Write a program that determines this number for the given grid.

Input. The first line contains two integers r and c (1 ≤ r, c ≤ 100) – the number of rows and columns in the grid.

The following r lines contain c integers each – the numbers printed on the grid. Each number is positive and does not exceed 1000.

Output. Output a single integer w – the total number of winning directions for the given grid.

Sample input	Sample output
3 4 5 3 9 10 1 8 8 2 4 3 4 3	25

SOLUTION

mathematics

Algorithm analysis

Let function check() computes the number of cells for which the left direction is winning. For each i-th line, find such a number of elements m[i][j] that all numbers in the line before it are strictly less than m[i][j].

Next, rotate the rectangular table clockwise by 90° and find the number of cells for which the left direction is winning. Rotate and count the cells two more times.

Example

In total we have:

Algorithm realization

Declare two arrays to store the table.

#define MAX 101

int m[MAX][MAX], m1[MAX][MAX];

Function check computes the number of cells for which the left direction is winning.

int check(void)

{

int i, j, s, res = 0;

for(i = 0; i < r; i++)

{

for(s = j = 0; j < c; j++)

if (m[i][j] > s)

{

s = m[i][j];

res++;

}

}

return res;

}

Rotate the rectangle clockwise. First, rotate and move the data from m to m1. Next, copy m1 to m.

void rotate(void)

{

int i, j, s;

memset(m1,0,sizeof(m1));

for(i = 0; i < r; i++)

for(j = 0; j < c; j++)

m1[j][r-i-1] = m[i][j];

memcpy(m,m1,sizeof(m));

s = r; r = c; c = s;

}

The main part of the program. Read the input data.

scanf("%d %d",&r,&c);

for(i = 0; i < r; i++)

for(j = 0; j < c; j++)

scanf("%d",&m[i][j]);

Add to res the number of cells for which the left direction is winning. Then rotate the table. Repeat 4 times (left, bottom, right, top directions).

res = 0;

for(i = 0; i < 4; i++)

{

res += check();

rotate();

}

Print the answer.

printf("%d\n",res);