Solution Idea

50072. City Grids

  • 此題建議開一個一維陣列去標記已走過的點,並要記得將陣列初始化,函式才可以提供多次的呼叫且不發生錯誤。
  • 解法提供如下程式碼,先確認是否能夠走向東邊或向北邊,並判斷完東北及北東是否存在以形成一個Grid後,才去做遞迴呼叫,如此便可減少錯誤的發生。
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
#include "City_Grid.h"
#include "stdio.h"
void move(City* city, int* pass, int* sum) {
    if(*(pass + city->label))
        return;
 
    *(pass + city->label) = 1;
    if(city->east != NULL && city->north != NULL) {
        if(city->east->north != NULL && city->north->east != NULL)
            ++(*sum);
        move(city->east, pass, sum);
        move(city->north, pass, sum);
    }
    else if(city->east != NULL)
        move(city->east, pass, sum);
    else if(city->north != NULL)
        move(city->north, pass, sum);
}
 
int City_Grid(City *capital) {
    int passed[10000] = {0};
    int N = 0;
    move(capital, passed, &N);
    return N;
}

Discussion