50072. City Grids

Task Description

Given a network of cities and roads, compute the number of city grids formed by four cities. There are $N$ cities that are all located at grid points, and any grid point can have only one city. The roads are all of length $1$, and only go to east or north. Note that not all roads need to be present even if two cities are next to each other. A city grids consists of four cities that are at the four corners of a unit grid, and the four surrendering roads.

You will be given a pointer to the capital, which is at location $(0, 0)$, and please compute the number of city grids in this country. We assume that the capital can go to any city in this country by roads. Each city struct will have two pointers to its neighboring city to the east and to the north, if they are present, and a label from $0$ to $N - 1$.

The prototype of the function you need to implement is as follows:

1
int City_Grid(City *capital);

Please compute the number of city grids as the return value.

Hint

Since the capital can reach all cities, you can start from the capital and traverse all cities by a simple recursion. Also all cities are labeled, so you can easily remember whether you have already visited them or not to save time. It is straightforward to check whether if a city is at a lower-left corner of a city grid, so you just check them one by one.

Header and Main Program

City_Grid.h

1
2
3
4
5
6
typedef struct City {
    int label;
    struct City *east, *north;
} City; 
 
int City_Grid(City *capital);

main.c (test)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "City_Grid.h"
#include <stdio.h>
#include <stdlib.h>
 
City* newNode(int label, City *E, City *N) {
    City *u = (City *) malloc(sizeof(City));
    u->label = label, u->east = E, u->north = N;
    return u;
}
 
int main() {
    City *capital = newNode(0, NULL, NULL);
    capital->east = newNode(1, newNode(3, NULL, NULL), NULL);
    capital->north = newNode(2, NULL, newNode(5, NULL, NULL));
    capital->east->north = capital->north->east = newNode(4, NULL, NULL);
 
    City *temp = capital->east->north;
    temp->east = newNode(6, NULL, NULL);
    temp->north = newNode(7, NULL, NULL);
    temp->east->north = temp->north->east = newNode(8, NULL, NULL);
 
    printf("%d\n", City_Grid(capital));
    return 0;
}

Compile

gcc -std=c99 -O2 City_Grid.c main.c -lm

Input Format

• $0 \lt N \lt 10000$

There are multiple test cases. The input country will be given as a pointer to the capital.

Output Format

Output number of city grids.

Sample Input

main.c (test)
 
5    7 一 8
|    |    |
2 一 4 一 6
|    |
0 一 1 一 3

Sample Output

2