学步园

URAL_1008

    没有太看懂题目描述的搜索顺序，但感觉应该是bfs，当然写成bfs也确实能AC。

    此外要注意题目中Input部分的说明，题意是在两种表示方法之间进行转换，因此如果输入Sample Output的内容就应该输出Sample Input的内容。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 110
#define INF 0x7fffffff
int N, g[MAXD][MAXD], vis[MAXD][MAXD], sx, sy, minx, miny, cnt;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
char ch[] = {'R', 'T', 'L', 'B'}, b[110];
struct Point
{
    int x, y;
}p[MAXD], q[MAXD];
char des[MAXD][5];
int cmp(const void *_p, const void *_q)
{
    Point *a = (Point *)_p, *b = (Point *)_q;
    if(a->x == b->x)
        return a->y < b->y ? -1 : 1;
    return a->x < b->x ? -1 : 1;
}
void initint()
{
    int i, j, k;
    memset(g, 0, sizeof(g));
    minx = miny = sx = INF;
    for(i = 0; i < N; i ++)
    {
        scanf("%d%d", &p[i].x, &p[i].y);
        if(p[i].x < minx)
            minx = p[i].x;
        if(p[i].y < miny)
            miny = p[i].y;
        if(p[i].x < sx || (p[i].x == sx) && p[i].y < sy)
            sx = p[i].x, sy = p[i].y;
    }
    for(i = 0; i < N; i ++)
        g[p[i].x - minx][p[i].y - miny] = 1;
}
void bfstochar(int sx, int sy)
{
    int i, j, k, front, rear, x, y, newx, newy, n;
    memset(vis, 0, sizeof(vis));
    memset(des, 0, sizeof(des));
    vis[sx][sy] = 1;
    front = rear = 0;
    q[rear].x = sx, q[rear].y = sy;
    ++ rear;
    while(front < rear)
    {
        x = q[front].x, y = q[front].y;
        n = 0;
        for(i = 0; i < 4; i ++)
        {
            newx = x + dx[i], newy = y + dy[i];
            if(newx >= 0 && newy >= 0 && g[newx][newy] && !vis[newx][newy])
            {
                vis[newx][newy] = 1;
                des[front][n ++] = ch[i];
                q[rear].x = newx, q[rear].y = newy;
                ++ rear;
            }
        }
        ++ front;
    }
}
void solveint()
{
    int i;
    bfstochar(sx - minx, sy - miny);
    printf("%d %d\n", sx, sy);
    for(i = 0; i < N - 1; i ++)
        printf("%s,\n", des[i]);
    printf("%s.\n", des[N - 1]);
}
void initchar()
{
    int i, j, k;
    for(i = 0; ; i ++)
    {
        scanf("%s", des[i]);
        if(des[i][0] == '.')
            break;
    }
}
void solvechar(int sx, int sy)
{
    int i, j, k, front, rear, x, y;
    cnt = 0;
    front = rear = 0;
    q[rear].x = sx, q[rear].y = sy;
    ++ rear;
    while(front < rear)
    {
        x = q[front].x, y = q[front].y;
        for(i = 0; des[front][i] != ',' && des[front][i] != '.'; i ++)
        {
            j = strchr(ch, des[front][i]) - ch;
            q[rear].x = x + dx[j], q[rear].y = y + dy[j];
            ++ rear;
        }
        ++ front;
    }
    qsort(q, rear, sizeof(q[0]), cmp);
    printf("%d\n", rear);
    for(i = 0; i < rear; i ++)
        printf("%d %d\n", q[i].x, q[i].y);
}
int main()
{
    gets(b);
    if(sscanf(b, "%d%d", &sx, &sy) == 2)
    {
        initchar();
        solvechar(sx, sy);
    }
    else
    {
        sscanf(b, "%d", &N);
        initint();
        solveint();
    }
    return 0;
}