Cプログラムで文字列を画面に出力するための最短パスを求める方法

文字列が与えられたとき、その文字列を画面上に出力するまでの最短パス(移動手順)を表示するCプログラムを紹介します。画面には、アルファベットが以下のように1行に5文字ずつ配置されているものとします。

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z

カーソルは初期状態で左上の「A」の位置におり、各文字の位置へ最短ルートで移動しながら文字を出力していきます。

例

入力: HUP
出力:
Move Down
Move Down
Move Down
destination reached
Move Left
Move Left
Move Down
Move Down
Move Down
destination reached
Move Up
destination reached

アプローチ

この問題では、アルファベットを n × n の行列として扱います。そして、現在位置と目的の文字の位置との差を計算し、その値に応じて次のように移動方向を決定します。

• 行の差が負の場合 → 上へ移動(Move Up)
• 行の差が正の場合 → 下へ移動(Move Down)
• 列の差が負の場合 → 左へ移動(Move Left)
• 列の差が正の場合 → 右へ移動(Move Right)

なお、各文字の座標は次の式で求められます。1行に5文字ずつ並んでいることを利用して、n1 が行番号、n2 が列番号に対応します。

行番号 n1 = (対象の文字 - 'A') / 5
列番号 n2 = (対象の文字 - 'B' + 1) % 5

アルゴリズム

START
Step 1 -> 関数 void printpath(char str[]) を宣言する
    変数 int i = 0、cx = 0、cy = 0 を宣言する
    str[i] != '\0' の間、以下を繰り返す
        int n1 = (str[i] - 'A') / 5 を計算する
        int n2 = (str[i] - 'B' + 1) % 5 を計算する
        cx > n1 の間、「Move Up」を出力し cx-- する
        cy > n2 の間、「Move Left」を出力し cy-- する
        cx < n1 の間、「Move Down」を出力し cx++ する
        cy < n2 の間、「Move Right」を出力し cy++ する
        「destination reached」を出力する
        i++ する
Step 2 -> main() 内で
    char str[] = {"HUP"} を宣言する
    printpath(str) を呼び出す
STOP

サンプルコード

#include <stdio.h>
void printpath(char str[]){
    int i = 0;
    // 位置 (0, 0) にある文字 'A' から開始する
    int cx = 0, cy = 0;
    while (str[i] != '\0'){
        // 次の文字の座標を求める
        int n1 = (str[i] - 'A') / 5;
        int n2 = (str[i] - 'B' + 1) % 5;
        // 目的地が上にある場合は上へ移動
        while (cx > n1){
            printf("Move Up\n");
            cx--;
        }
        // 目的地が左にある場合は左へ移動
        while (cy > n2){
            printf("Move Left\n");
            cy--;
        }
        // 目的地が下にある場合は下へ移動
        while (cx < n1){
            printf("Move Down\n");
            cx++;
        }
        // 目的地が右にある場合は右へ移動
        while (cy < n2){
            printf("Move Right\n");
            cy++;
        }
        // この時点で目的地に到達
        printf("destination reached\n");
        i++;
    }
}
int main(int argc, char const *argv[]){
    char str[] = {"HUP"};
    printpath(str);
    return 0;
}

出力

上記のプログラムを実行すると、次のような出力が得られます。

Move Down
Move Down
Move Down
destination reached
Move Left
Move Left
Move Down
Move Down
Move Down
destination reached
Move Up
destination reached

このように、行列上の文字位置を行と列の差から判定することで、任意の文字列に対してその印字に必要な移動手順(最短パス)を順番に表示することができます。