Bài toán
Cho chuỗi ký tự in hoa, tìm đường đi ngắn nhất trên bàn phím lưới 5×5 (A-Z) để gõ chuỗi. Bắt đầu từ 'A' (0,0). Di chuyển: Up, Down, Left, Right.
Bàn phím
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
Ví dụ
Input: "HUP" Output: Move Down (x3) → destination reached Move Left (x2), Move Down (x3) → destination reached Move Up → destination reached
Thuật toán
- Tính tọa độ ký tự: row = (ch-'A')/5, col = (ch-'B'+1)%5
- So sánh tọa độ hiện tại (cx,cy) với đích (n1,n2)
- Di chuyển từng bước: cx>n1 → Up, cy>n2 → Left, cx
- In "destination reached" khi tới
Mã nguồn C
#include <stdio.h>
void printpath(char str[]) {
int i=0, 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() {
char str[] = "HUP";
printpath(str);
return 0;
}
Kết quả
Move Down Move Down Move Down destination reached Move Left Move Left Move Down Move Down Move Down destination reached Move Up destination reached