Problem 10452 Marcus

給你一陣列，要你求出從字元 '@'( 一定在最後一排 )到字元 '#'( 一定在第一排 )，按照字串 "IEHOVA" 走法，列出怎麼走才會走的到字元 '#' 的走法。

所以先寫好一字串，讓它走一步可以比對索引字元，若不對，則不走；若走到，則印出。用一遞迴函式實現，i, j 為目前位置，index 為目前字串索引：

#define SIZE 8
#define LEN 7
int n, row, col, sI, sJ, eI, eJ;

char letters[LEN + 1] = {'@', 'I', 'E', 'H', 'O', 'V', 'A', '#'};
char path[LEN];
char stone[SIZE][SIZE + 1];
void visit(int i, int j, int index)
{
    if (letters[index] != stone[i][j]) return;
    if (i == eI && j == eJ)
    {
        int k;
        
        if (path[0] == 'r') printf("right");
        else if (path[0] == 'l') printf("left");
        else if (path[0] == 'f') printf("forth");
        
        for (k = 1; k < LEN; k ++)
        {
            if (path[k] == 'r') printf(" right");
            else if (path[k] == 'l') printf(" left");
            else if (path[k] == 'f') printf(" forth");
        }
        printf("\n");
    }
    /* 左 */
    if (j - 1 >= 0) path[index] = 'l', visit(i, j - 1, index + 1);
    /* 右 */
    if (j + 1 < col) path[index] = 'r', visit(i, j + 1, index + 1);
    /* 前 */
    if (i - 1 >= 0) path[index] = 'f', visit(i - 1, j, index + 1);
}

最後，在主程式如此呼叫：

scanf("%d %d", &row, &col);  
for (i = 0; i < row; i ++)
{
    scanf("%s", stone[i]);
    if (i == 0)
    { 
        for (j = 0; j < col; j ++)
            if (stone[i][j] == '#') eI = i, eJ = j;
    }
    if (i == row - 1)
    {
        for (j = 0; j < col; j ++)
            if (stone[i][j] == '@') sI = i, sJ = j;
    }
}
visit(sI, sJ, 0);

By David.K

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