http://zerosea.tfcis.org:8080/JudgeOnline/showproblem?problem_id=1149

這題最難的地方在於方向 (我是J睿捏我才會的)

1. 起點放入queue

2. 從queue拿出點 四周可以通行的點步數都+1

3. 固定方向把接下來的點都放入queue 直到不能放為止
       重點是要記得紀錄步數和把點戳成黑洞

感謝jghs1328幫我debug好久..

#include <stdio.h>  

typedef struct {  
 int x;  
 int y;  
} point;  
point que[1000000];  
point s, t;  
char space[1002][1002];  
int cost[1002][1002];  
int dx[4] = {1, 0, -1, 0};  
int dy[4] = {0, 1, 0, -1};  
int front, rear;  
int main()  
{  
 int n, i, j;  
 scanf("%d\n", &n);  
 for (i = 1; i <= n; i++) {  
 for (j = 1; j <= n; j++) {  
 space[i][j] = getchar();  
 if (space[i][j] == '1') {  
 space[i][j] = 0;  
 } else if (space[i][j] == 'A') {  
 s.x = i;  
 s.y = j;  
 } else if (space[i][j] == 'B') {  
 t.x = i;  
 t.y = j;  
 }  
 }  
 getchar();  
 }  
 front = rear = 0;  
 que[rear++] = s;  
 space[s.x][s.y] = 0;  
 cost[s.x][s.y] = -1;  
 while (front < rear) {  
 point p = que[front++];  
 point n;  
 space[p.x][p.y] = 0;  
 if (p.x == t.x && p.y == t.y) {  
 break;  
 }  
 for (i = 0; i < 4; i++) {  
 n.x = p.x + dx[i];  
 n.y = p.y + dy[i];  
 if (space[n.x][n.y] == 0) {  
 continue;  
 }  
 que[rear++] = n;  
 cost[n.x][n.y] = cost[p.x][p.y] + 1;  
 space[n.x][n.y] = 0;  
 int tmp = cost[n.x][n.y];  
 n.x += dx[i];  
 n.y += dy[i];  
 while (space[n.x][n.y] != 0) {  
 que[rear++] = n;  
 cost[n.x][n.y] = tmp;  
 space[n.x][n.y] = 0;  
 n.x += dx[i];  
 n.y += dy[i];  
 }  
 }  
 }  
 printf("%d\n", cost[t.x][t.y]);  
 return 0;  
}