Description

In this problem, you are asked to design two functions
    1.

unsigned** new_2d_array(unsigned n,unsigned m);

malloc an n*m 2D unsigned array, and then return its address. The main function will check the correctness of your array.

    2.

void delete_2d_array(unsigned **arr);

Free the memory space of your array that was previously allocated by using malloc. Be careful about the memory uage of your program allocated dynamically so as to avoid MLE.

The two functions have been declared in function.h, and you are asked to complete the function definitions in function.c.

Your program should construct the 2D array by using only two malloc function calls. Notice that malloc is a time-consuming operation.

Note: for OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose C compiler) 

       Step 2. Check the results and debug your program if necessary.

Input

Please refer to the main function.

The input only has one line, consisting of four positive integers t,n,m,r separated by space characters, where t is the number of tests, (n,m) represents the array size, and r is a parameter for testing. 

Note that n*m<=100000000 and t*n*m<=100000000

Output

In order to test your array's correctness, we will use your array to do some computations and output the results.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Red Cape Flying Cat has a very large character grid, and he wants to know how many distinct characters are in a given rectangular region.

The grid is 0-indexed. The cell at row r and column c is denoted as (r, c), where (0, 0) is the top-left corner. A rectangular region from (r1, c1) to (r2, c2) includes all cells (r, c) such that r1 <= r <= r2 and c1 <= c <= c2.

Since there are many queries, please help him write an efficient program to answer these questions.

Hint:
This is a Partial Judge Problem:
0. You will be provided 2 files below: 'main.c', 'function.h'. You should only upload your 'solver' function inside your '.c' file.
1. The 'main.c' file contains input, output, and function call, the 'function.h' file contains the declaration of 'solver' function, and your '.c' file should contain the implementation of 'solver' function.
2. You can compile multiple files by command, ex: 'gcc main.c function.h your_code.c', or create a project in your IDE.
3. Remember to include 'function.h'.
 

main.c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <stdio.h>
#include "function.h"

#define MAXN 455
#define MAXM 455
#define MAXQ 2000005

char grid[MAXN][MAXM];
char *grid_ptr[MAXN];

int queries[MAXQ][4];
int *queries_ptr[MAXQ];

int results[MAXQ];
int *results_ptr[MAXQ];

int prefix[26][MAXN][MAXM];
int *prefix_row[26][MAXN];
int **prefix_ptr[26];

int main() {
    int n, m, q;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
        grid_ptr[i] = grid[i];
    }

    scanf("%d", &q);

    for (int i = 0; i < q; i++) {
        scanf("%d %d %d %d", &queries[i][0], &queries[i][1], &queries[i][2], &queries[i][3]);
        queries_ptr[i] = queries[i];
        results[i] = 0;
        results_ptr[i] = &results[i];
    }

    for (int c = 0; c < 26; c++) {
        for (int i = 0; i <= n; i++) {
            prefix_row[c][i] = prefix[c][i];
        }
        prefix_ptr[c] = prefix_row[c];
    }

    solver(grid_ptr, n, m, queries_ptr, results_ptr, q, prefix_ptr);

    for (int i = 0; i < q; i++) {
        printf("%d\n", results[i]);
    }

    return 0;
}

function.h

1
2
3
4
5
6

#ifndef FUNCTION_H
#define FUNCTION_H

void solver(char **s, int n, int m, int **queries, int **results, int q, int ***prefix);

#endif

It is recommended to use 2D prefix sum to solve this problem. Build a 2D prefix sum array for each character.

The expected time complexity is O(26 * N * M + 26 * Q).

Note: The 'prefix' parameter is a pre-allocated 3D array space. You may use it to build your 2D prefix sum, but it is not mandatory.

Input

The first line contains two integers N and M, representing the number of rows and columns of the grid.

The next N lines each contain a string of length M, consisting of only lowercase English letters.

The next line contains an integer Q, representing the number of queries.

The next Q lines each contain four integers r1, c1, r2, c2, representing a query for the rectangular region from (r1, c1) to (r2, c2). (0-indexed)

It is guaranteed that:
0. 1 <= N, M <= 450
1. 1 <= Q <= 2 * 10^6
2. 0 <= r1 <= r2 < N
3. 0 <= c1 <= c2 < M

Subtasks:
- Subtask 1 (20%, 2 testcases): N <= 150, M <= 150, Q <= 15000
- Subtask 2 (40%, 4 testcases): N = 1
- Subtask 3 (20%, 2 testcases): both r1 and c1=0 for all queries
- Subtask 4 (20%, 2 testcases): No additional constraints

Output

For each query, output one line containing the number of distinct characters in the rectangular region.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss