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
123456 typedef
struct
City {
int
label;
struct
City *east, *north;
} City;
int
City_Grid(City *capital);
main.c (test)
123456789101112131415161718192021222324 #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