Problem 825 Walking on the Safe Side，走最省的路

其實一看圖就知道，題目會給你橫縱各有幾條路，再給你幾個中斷點，問你有幾條最省的路從左上角到右下角。所以我們可以建立陣列，可以走的路訂為 0，不可走的路訂為 1。C 語言程式碼如下：

char str[200], *pch;
int road[101][101];
int i, j, k;
scanf("%d %d", &W, &N);
getchar();
memset(road, 0, sizeof(road));

for (i = 0; i < W; i ++)
{
    gets(str);
    pch = strtok(str, " ");
    sscanf(pch, "%d", &j);
    pch = strtok(NULL, " ");
    while (pch != NULL)
    {
        sscanf(pch, "%d", &k);
        pch = strtok(NULL, " ");
        road[j - 1][k - 1] = 1;
    } 
}

再來，用回溯演算法寫一函式讓它去嘗試每一條可以走的路，最省的路只能走右或走下，所以只需要嘗試這兩條路即可。C 語言程式碼如下：

void visit(int road[][101], int i, int j)
{
    road[i][j] = 1;
    
    if (i == W - 1 && j == N - 1) count ++;
    
    if (road[i][j + 1] == 0 && j < N) visit(road, i, j + 1);
    if (road[i + 1][j] == 0 && i < W) visit(road, i + 1, j);    
    
    road[i][j] = 0;
}

最後，只須再主程式呼叫函式並且印出：

visit(road, 0, 0);
printf("%d\n", count);

By David.K

p825題目連結
回ACM題庫目錄
回首頁