Wednesday, March 7, 2012

[code] UPRC-1149 太空船(TOI初選2007pD)

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;
}
 

2 comments:

  1. joshua 大牛ㄝ

    ReplyDelete
  2. joshua是大牛眼中的大牛,所以是大牛

    ReplyDelete