URAL 1008. Image Encoding

Author: 2015-08-23

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1008

1008. Image Encoding

Time limit: 2.0 second
Memory limit: 64 MB

Problem illustration

There are several ways to encode an image. In this problem we will consider two representations of an image. We assume that the image consists of black and white pixels. There is at least one black pixel and all black pixels are connected with their sides. Coordinates of black pixels are not less than 1 and not greater than 10. An example of such an image is at the figure.
Both representations describe arrangement of black pixels only.
At the first representation we specify in the first line number of black pixels and coordinates of each black pixel in the following lines. Pixels are listed in order of increasing X. In case of equality of X they are listed in order of increasing Y. Image at the figure is encoded as follows:
6
2 3
2 4
3 3
3 4
4 2
4 3
At the second representation we specify in the first line coordinates of the lowest left black pixel. Each of the following lines contains a description of neighbors for one of the pixels. At first, neighbors of the lowest left pixel are specified, then neighbors of its first neighbor (if it exists) are specified, then neighbors of its second neighbor (if it also exists) follow. When all its neighbors are described the description of the neighbors of its first neighbor follows. The description of the neighbors of its second neighbor follows then and so on.
Each descriptive line contains at most one letter for each neighbor: R for the right, T for the top, L for the left, B for the bottom. If the neighbor was already specified it is not included into the descriptive line and vice-versa. Also there is only one descriptive line for each pixel. Neighbors are listed counter-clockwise starting with the right. Each descriptive line except the last ends with a comma. The last line ends with a full stop. Image at the figure is encoded as follows:
2 3
RT,
RT,
,
B,
,
.
There are no leading or tailing spaces in any representation. There is exactly one space between X and Y coordinates.

Input

One representation of the image will be given to your program in the input.

Output

Your program has to write other representation of the image to the output.

Sample

input output 
6
2 3
2 4
3 3
3 4
4 2
4 3

2 3
RT,
RT,
,
B,
,
.
Problem Source: Third Open USTU Collegiate Programming Contest (PhysTech Cup), March 18, 2000

2. 思路

规定一个位图的两种编码方式，给出其中一种编码，求另一种编码。

第一种编码方式直接是坐标，很简单。第二种编码方式是给出一个参考点的坐标，其他点以相对位置的方式表示，可以看做是一个BFS的过程。

比较麻烦的一点在于，给出的编码可能是两种方式中的任意一种，求使用另一种方式编码的结果，两种方式的编码和解码都要考虑。

3.代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_COORDINATE 10
#define MAX_POINTS ((MAX_COORDINATE + 1) * (MAX_COORDINATE + 1))

typedef char Image[MAX_COORDINATE + 1][MAX_COORDINATE + 1];

void solveE1g();
int inputImageFirst(Image image, int blackPixelNum, int *startX, int *startY);
int inputImageSecond(Image image, int startX, int startY);
void initImage(Image image);
void printSecondReprest(Image image, int blackPixelNum, int startX, int startY);
void printFirst(Image image, int startX, int startY, int blackPixelNum);
int hasBlackPixel(Image image, int x, int y);
void printImage(Image image, int size);

int main() {
    solveE1g();
    return 0;
}


Image image;
void solveE1g() {
    int blackPixelNum, startX, startY;
    char firstLine[10];

    scanf("%[^\n]", firstLine);
    if (strstr(firstLine, " ") == NULL) {
        sscanf(firstLine, "%d", &blackPixelNum);
        if (blackPixelNum == 0)
            return;
        inputImageFirst(image, blackPixelNum, &startX, &startY);
        printSecondReprest(image, blackPixelNum, startX, startY);
    } else {
        sscanf(firstLine, "%d %d", &startX, &startY);
        blackPixelNum = inputImageSecond(image, startX, startY);
        //printImage(image, 5);
        printFirst(image, startX, startY, blackPixelNum);
    }
}

int inputImageSecond(Image image, int startX, int startY) {
    int hasMore = 1, front = 0, rear = 0, currX, currY;
    char currChar;
    unsigned char queueX[MAX_POINTS], queueY[MAX_POINTS];

    initImage(image);
    
    queueX[rear] = startX;
    queueY[rear] = startY;
    ++rear;
    image[startY][startX] = 1;

    while (1) {
        currX = queueX[front];
        currY = queueY[front];
        ++front;

        while (1) {
            scanf("%c", &currChar);
            if (currChar == 'T') {
                queueX[rear] = currX;
                queueY[rear] = currY + 1;
                ++rear;
                image[currY + 1][currX] = 1;
            }
            else if (currChar == 'B') {
                queueX[rear] = currX;
                queueY[rear] = currY - 1;
                ++rear;
                image[currY - 1][currX] = 1;
            }
            else if (currChar == 'L') {
                queueX[rear] = currX - 1;
                queueY[rear] = currY;
                ++rear;
                image[currY][currX - 1] = 1;
            }
            else if (currChar == 'R') {
                queueX[rear] = currX + 1;
                queueY[rear] = currY;
                ++rear;
                image[currY][currX + 1] = 1;
            }
            else if (currChar == ',') {
                break;
            }
            else if (currChar == '.') {
                return front;
            }
        }
    }
}

void printFirst(Image image, int startX, int startY, int blackPixelNum) {
    int i, j, cnt = 0;

    printf("%d\n", blackPixelNum);
    for (i = 0; i <= MAX_COORDINATE && cnt < blackPixelNum; ++i) {
        for (j = 0; j <= MAX_COORDINATE && cnt < blackPixelNum; ++j) {
            if (image[j][i] == 1) {
                printf("%d %d\n", i, j);
                ++cnt;
            }
        }
    }
}

int inputImageFirst(Image image, int blackPixelNum, int *startX, int *startY) {
    int i, x, y;

    initImage(image);

    for (i = 0; i < blackPixelNum; ++i) {
        scanf("%d %d", &x, &y);
        image[y][x] = 1;
        if (i == 0) {
            *startX = x;
            *startY = y;
        }
    }

    return 0;
}

void initImage(Image image) {
    int i, j;

    for (i = 1; i < MAX_COORDINATE + 1; ++i) {
        for (j = 1; j < MAX_COORDINATE + 1; ++j) {
            image[i][j] = 0;
        }
    }
}

void printSecondReprest(Image image, int blackPixelNum, int startX, int startY) {
    int front = 0, rear = 0, currentX, currentY, nextX, nextY;
    unsigned char queueX[MAX_POINTS], queueY[MAX_POINTS];

    printf("%d %d\n", startX, startY);

    queueX[rear] = startX;
    queueY[rear] = startY;
    ++rear;
    image[startY][startX] = 0;

    while (front < rear) {
        currentX = queueX[front];
        currentY = queueY[front];
        ++front;

        // Check right
        nextX = currentX + 1;
        nextY = currentY;
        if (hasBlackPixel(image, nextX, nextY)) {
            queueX[rear] = nextX;
            queueY[rear] = nextY;
            ++rear;
            image[nextY][nextX] = 0;
            printf("R");
        }

        // Check top
        nextX = currentX;
        nextY = currentY + 1;
        if (hasBlackPixel(image, nextX, nextY)) {
            queueX[rear] = nextX;
            queueY[rear] = nextY;
            ++rear;
            image[nextY][nextX] = 0;
            printf("T");
        }

        // Check left
        nextX = currentX - 1;
        nextY = currentY; //Y-axis is upside down.
        if (hasBlackPixel(image, nextX, nextY)) {
            queueX[rear] = nextX;
            queueY[rear] = nextY;
            ++rear;
            image[nextY][nextX] = 0;
            printf("L");
        }

        // Check bottom
        nextX = currentX;
        nextY = currentY - 1;
        if (hasBlackPixel(image, nextX, nextY)) {
            queueX[rear] = nextX;
            queueY[rear] = nextY;
            ++rear;
            image[nextY][nextX] = 0;
            printf("B");
        }
        if (front == rear)
            printf(".\n");
        else
            printf(",\n");
    }
}

int hasBlackPixel(Image image, int x, int y) {
    if (x < 1 || x > MAX_COORDINATE || y < 1 || y > MAX_COORDINATE) {
        return 0;
    }
    else {
        return image[y][x];
    }
}

void printImage(Image image, int size) {
    int i, j;

    for (i = size; i >= 1; --i) {
        for (j = 1; j <= size; ++j) {
            printf("%d ", image[i][j]);
        }
        printf("\n");
    }
}