後來DS看完array了,
剛好exercise有一題也是knight move,
想說做完這題習題應該就能解這題ACM了,
結果悲劇,根本是不一樣的問題。
習題的題目:隨便給一個點,繞完西洋棋上每個點剛剛好一次。
這題:給兩點,由A點到B點的最短移動次數。
後來想到一種方法,不如從起始點A開始填數字(數字表示移動次數),
把西洋棋盤填滿,這樣就能知道A到B的移動次數。
但是有個問題,不知道能不能依序移動。
(後來看別人的作法,是可以依序移動)
依序移動的意思是,從某個點開始1, 2, 3一直往上填。
所以作法上保守一點,
就從A點開始,填滿所有的1,再從每個1中依序填滿所有的2,以此類推。
每填好一個,就丟到stack中,當所有的1都丟到stack中後,
最先丟進去的1要先拿出來用。依此類推。
有點first in first out的感覺。
應該叫quene不叫stack。
/* ACM 439 Knight Moves * mythnc * 2011/11/29 16:49:26 * run time: 0.024 */ #include <stdio.h> #include <string.h> #define MAXCHAR 3 /* 2 + '\0' */ #define MAXS 8 #define RANGE(X) X >= 0 && X < MAXS typedef struct point { int x; /* row */ int y; /* col */ } Point; Point stoc(char *); void draw(int (*)[], Point); void filln(int (*)[], Point, Point); int count; Point stack[MAXS * MAXS]; int main(void) { char start[MAXCHAR], end[MAXCHAR]; int square[MAXS][MAXS]; Point from, to; while (scanf("%s %s", start, end) == 2) { /* init */ memset(square, 0, sizeof(square)); from = stoc(start); to = stoc(end); draw(square, from); printf("To get from %s to %s takes %d knight moves.\n", start, end, square[to.x][to.y]); } return 0; } /* stoc: string change to coordinate */ Point stoc(char *s) { Point pt; pt.x = s[1] - '1'; pt.y = s[0] - 'a'; return pt; } /* draw: fill square with numbers */ void draw(int (*s)[MAXS], Point pt) { int i, j; Point origin; origin.x = pt.x; origin.y = pt.y; count = 0; filln(s, pt, origin); for (i = 0; i < count; i++) { pt.x = stack[i].x; pt.y = stack[i].y; filln(s, pt, origin); } } /* filln: fill blocks to number n */ void filln(int (*s)[MAXS], Point pt, Point o) { int i, x, y, n; int movex[] = {-2, -1, 1, 2, 2, 1, -1, -2}; int movey[] = {1, 2, 2, 1, -1, -2, -2, -1}; n = s[pt.x][pt.y] + 1; for (i = 0; i < 8; i++) { x = pt.x + movex[i]; y = pt.y + movey[i]; if (RANGE(x) && RANGE(y) && s[x][y] == 0 && (x != o.x || y != o.y)) { s[x][y] = n; stack[count].x = x; stack[count].y = y; count++; } } }
沒有留言:
張貼留言