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 located at grid points, and any grid point can have only one city. The roads are all of the lengths $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 grid consists of four cities 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 road. Each city struct will have two pointers to its neighboring city to the east and 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 a city is at a lower-left corner of a city grid, so you 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 is a pointer to the capital.

Output Format

Output the number of city grids.

Sample Input

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

Sample Output

2