URAL 1008 Image Encoding (BFS)

#include <stdio.h>

#define SIZE 10

int n;

int leftBottomX, leftBottomY;
int x, y;

int image[SIZE + 1][SIZE + 1];


typedef struct{
    int x;
    int y;
} PIXEL;
PIXEL queue[SIZE * SIZE + 1];
int head, tail;

PIXEL pixelPoped, pixelPushed;

int pixelVisited[SIZE + 1][SIZE + 1];

int directions[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

void BFS1( ){
    int leftBottomPixelFound = 0;
    int indexOfBlack;
    for (indexOfBlack = 1; indexOfBlack <= n; indexOfBlack++){
        scanf("%d %d", &x, &y);
        image[x][y] = 1;
        if (!leftBottomPixelFound){
            leftBottomPixelFound = 1;
            leftBottomX = x;
            leftBottomY = y;

        }
    }

    printf("%d %d
", leftBottomX, leftBottomY); pixelPushed.x = leftBottomX; pixelPushed.y = leftBottomY; pixelVisited[leftBottomX][leftBottomY] = 1; queue[tail++] = pixelPushed; while (head < tail){ pixelPoped = queue[head++]; int indexOfDirection; for (indexOfDirection = 0; indexOfDirection < 4; indexOfDirection++){ x = pixelPoped.x + directions[indexOfDirection][0]; y = pixelPoped.y + directions[indexOfDirection][1]; if (image[x][y] == 0 || x < 1 || x > SIZE || y < 1 || y > SIZE || pixelVisited[x][y] == 1) continue; pixelVisited[x][y] = 1; char charPrinted; if (indexOfDirection == 0) charPrinted = 'R'; else if (indexOfDirection == 1) charPrinted = 'T'; else if (indexOfDirection == 2) charPrinted = 'L'; else if (indexOfDirection == 3) charPrinted = 'B'; printf("%c", charPrinted); pixelVisited[x][y] = 1; pixelPushed.x = x; pixelPushed.y = y; queue[tail++] = pixelPushed; } printf("%c
", head == tail ? '.' : ','); } } void BFS2(){ leftBottomX = n; scanf("%d", &leftBottomY); image[leftBottomX][leftBottomY] = 1; pixelPushed.x = leftBottomX; pixelPushed.y = leftBottomY; queue[tail++] = pixelPushed; while (head < tail){ pixelPoped = queue[head++]; char directionStr[6]; scanf("%s", directionStr); int indexOfChar; for (indexOfChar = 0; directionStr[indexOfChar] != '\0'; indexOfChar++){ if (directionStr[indexOfChar] == '.' || directionStr[indexOfChar] == ',') break; int indexOfDiretion; if (directionStr[indexOfChar] == 'R') indexOfDiretion = 0; else if (directionStr[indexOfChar] == 'T') indexOfDiretion = 1; else if (directionStr[indexOfChar] == 'L') indexOfDiretion = 2; else if (directionStr[indexOfChar] == 'B') indexOfDiretion = 3; x = pixelPoped.x + directions[indexOfDiretion][0]; y = pixelPoped.y + directions[indexOfDiretion][1]; if (image[x][y] == 1) continue; image[x][y] = 1; pixelPushed.x = x; pixelPushed.y = y; queue[tail++] = pixelPushed; } } int numOfBlacks = head; printf("%d
", numOfBlacks); for (x = 1; x <= SIZE; x++) for (y = 1; y <= SIZE; y++) if (image[x][y] == 1) printf("%d %d
", x, y); } int main() { scanf("%d", &n); char cha = getchar(); if (cha == '
') BFS1(); else BFS2(); return 0; }

좋은 웹페이지 즐겨찾기