โจทย์
กำหนดสตริง ให้หาเส้นทางสั้นที่สุดบนคีย์บอร์ดหน้าจอที่จัดเรียงตัวอักษร A-Z ในกริด 5×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
ตัวอย่าง
Input: "HUP" Output: Move Down (3 ครั้ง) → destination reached Move Left (2 ครั้ง) → Move Down (3 ครั้ง) → destination reached Move Up (1 ครั้ง) → destination reached
อัลกอริทึม
- เริ่มที่ 'A' ตำแหน่ง (0,0)
- หาพิกัดของตัวอักษรเป้าหมาย: row = (ch - 'A') / 5, col = (ch - 'B' + 1) % 5
- เปรียบเทียบพิกัดปัจจุบัน (cx, cy) กับเป้าหมาย (n1, n2)
- cx > n1: Move Up, cx < n1: Move Down, cy > n2: Move Left, cy < n2: Move Right
- พิมพ์ "destination reached" เมื่อถึงตัวอักษร
- ทำซ้ำทุกตัวอักษรในสตริง
โค้ดภาษา C
#include <stdio.h>
void printpath(char str[]) {
int i = 0;
int cx = 0, cy = 0; // เริ่มที่ A (0,0)
while (str[i] != '\0') {
int n1 = (str[i] - 'A') / 5; // target row
int n2 = (str[i] - 'B' + 1) % 5; // target col
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;
}ผลลัพธ์
Move Down Move Down Move Down destination reached Move Left Move Left Move Down Move Down Move Down destination reached Move Up destination reached
