user 청소봇

테캐 100개, 제한시간 3초

메모리: 힙, 정적 메모리 합쳐서 256메가 바이트, 스택 메모리 1메가

 

정사각형 맵이 있고, 1이 써있으면 천장에 무늬, 0은 무늬없는 곳, 9는 벽 단 맵의 테두리는 벽.

청소로봇은 2바이2의 크기를 갖고 맵 상에서 이 로봇의 위치와 방향을 찾는 문제

 

메인에서 두가지 함수를 제공함

보이드 스캔

인트 이미지

로봇과 주변을 포함한 4바이4의 맵의 값을 알려줌. 로봇의 방향에 따라 이미지 배열에 기록되는 값이 다름

방향에 맞게 회전된 값이 들어간다고 보면 됨

 

불 컨트롤 int cmd

로봇을 앞으로 나아가게 하거나, 오른쪽 회전을 하는 명령임

고 명령이 fail 되면, false를 리턴함

 

2가지 API를 활용하여, 아래 API를 구현하셈

1 보이느 이닛 int n, const int map[][]

pos find_where()

청소로봇의 유일한 좌표 2바이2 좌상단 셀 좌표와 방향을 return

struct pos{

unsigned char r,c;

unsigned char dir;

};

접수요

 

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

#define MAX_N 200 // map 크기 
#define MAX_QUERY_CNT MAX_N // query_cnt ?
#define NO_MUNI 0 // 무늬 없는 것
#define MUNI 1 // 무늬
#define WALL 9 // 벽
#define GOFORWARD 0 // 앞으로
#define TURNRIGHT 1 // 오른쪽으로 돌기

enum DIR { UP, RIGHT, DOWN, LEFT, MAX_DIR }; // 위, 오른, 아래, 왼, max_dir 체크

static int dr[MAX_DIR] = { 0, 0, 1, 1 }; // 
static int dc[MAX_DIR] = { 0, 1, 1, 0 }; // 

static int dr2[MAX_DIR] = { -1, 0, 1, 0 }; //
static int dc2[MAX_DIR] = { 0, 1, 0, -1 }; // 도는데 필요함

struct POS {
    unsigned char r, c; // x, y 좌표로 사용하는 듯
    unsigned char dir; // 방향 정보 
};
static POS robot_arr[MAX_QUERY_CNT]; // 어디에 사용
static POS *robot; // 포인터를

static int N;   // 맵의 크기 10 <= N <= 200
static int M;   // N / 2
static int P;   // 확률로 만드는 것임 : 1(= 0.1) <= P <= 5(= 0.5)
static int Q;   // 이것도 문제를 만드는데 사용되는 변수인가. query : N

static int map[MAX_N][MAX_N]; // 맵을 저장함

static int tc; // test_case

extern void init(int n, const int map[MAX_N][MAX_N]); // 처음 들어가는 파라미터 n? 
extern POS find_where(); // row, col, dir 을 return 함

///////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////////////////

void scan(int image[4][4])
{
    if (robot->dir == UP) {
        for (int row = 0, r = robot->r - 1; row < 4; ++row, ++r) {
            for (register int col = 0, c = robot->c - 1; col < 4; ++col, ++c) {
                image[row][col] = map[r][c];
            }
        }
    }
    else if (robot->dir == DOWN) {
        for (int row = 0, r = robot->r + 1; row < 4; ++row, --r) {
            for (register int col = 0, c = robot->c + 1; col < 4; ++col, --c) {
                image[row][col] = map[r][c];
            }
        }
    }
    else if (robot->dir == RIGHT) {
        for (int row = 0, c = robot->c + 1; row < 4; ++row, --c) {
            for (register int col = 0, r = robot->r - 1; col < 4; ++col, ++r) {
                image[row][col] = map[r][c];
            }
        }
    }
    else { // robot->dir == LEFT
        for (int row = 0, c = robot->c - 1; row < 4; ++row, ++c) {
            for (register int col = 0, r = robot->r + 1; col < 4; ++col, --r) {
                image[row][col] = map[r][c];
            }
        }
    }
}

bool control(int cmd) {
    if (cmd == GOFORWARD)
    {
        if (robot->dir == UP) {
            if (map[robot->r - 1][robot->c] == WALL || map[robot->r - 1][robot->c + 1] == WALL) return false;
            robot->r--;
        }
        else if (robot->dir == DOWN) {
            if (map[robot->r + 1][robot->c] == WALL || map[robot->r + 1][robot->c - 1] == WALL) return false;
            robot->r++;
        }
        else if (robot->dir == RIGHT) {
            if (map[robot->r][robot->c + 1] == WALL || map[robot->r + 1][robot->c + 1] == WALL) return false;
            robot->c++;
        }
        else if (robot->dir == LEFT) {
            if (map[robot->r][robot->c - 1] == WALL || map[robot->r + 1][robot->c - 1] == WALL) return false;
            robot->c--;
        }
    }
    else { // cmd == TURNRIGHT
        robot->dir++; if (robot->dir == MAX_DIR) robot->dir = UP;
        robot->r += dr2[robot->dir];
        robot->c += dc2[robot->dir];
    }

    return true;
}

inline void make_map() {
    // 입력받은 N을 기준으로 벽을 세우고
    for (register int i = 0; i < N; ++i) map[0][i] = map[N - 1][i] = map[i][0] = map[i][N - 1] = WALL;

    // N을 기준으로, 안에 1을 채움
    for (register int r = 1; r < N - 1; ++r) {
        for (register int c = 1; c < N - 1; ++c) {
            map[r][c] = ((rand() % 10) < P) ? MUNI : NO_MUNI;
        }
    }

    // rand 벽을 추가함
    register int r, c;
    int mod = N - 2;
    int cnt = M;
    while (cnt--) {
        do {
            r = rand() % mod + 1;
            c = rand() % mod + 1;
        } while (map[r][c] == WALL);

        map[r][c] = WALL;
    }
}

inline bool is_OK(int r, int c)
{
    for (register int _r = r; _r <= r + 1; ++_r) {
        for (register int _c = c; _c <= c + 1; ++_c) {
            if (map[_r][_c] == WALL) return false;
        }
    }

    if (map[r - 1][c] != WALL && map[r - 1][c + 1] != WALL) return true;
    if (map[r][c - 1] != WALL && map[r + 1][c - 1] != WALL) return true;
    if (map[r][c + 2] != WALL && map[r + 1][c + 2] != WALL) return true;
    if (map[r + 2][c] != WALL && map[r + 2][c + 1] != WALL) return true;

    return false;
}

inline void make_robot_pos()
{
    int r, c;
    int mod = N - 3;
    for (int idx = 0; idx < Q; ++idx) {
        do {
            r = rand() % mod + 1;
            c = rand() % mod + 1;
        } while (!is_OK(r, c));

        robot_arr[idx].r = r;
        robot_arr[idx].c = c;

        robot_arr[idx].dir = rand() % MAX_DIR;
        robot_arr[idx].r += dr[robot_arr[idx].dir];
        robot_arr[idx].c += dc[robot_arr[idx].dir];
    }
}

bool run()
{
    make_map(); // map 을 만듦
    make_robot_pos(); // robot 의 위치를 지정함

    // 해쉬 세팅 완료
    init(N, map);

    for (int q = 0; q < Q; ++q) {
        robot = &robot_arr[q];
        POS user_ans = find_where();
#if 1
        if (robot->dir != user_ans.dir || robot->r != user_ans.r || robot->c != user_ans.c) return false;
#else
        if (robot->dir != user_ans.dir || robot->r != user_ans.r || robot->c != user_ans.c) {
            printf("*** wrong answer @ tc(%d), query(%d) :  ", tc, q);
            printf("robot: %d %d %d vs. ", robot->dir, robot->r, robot->c);
            printf("user: %d %d %d ***\n", user_ans.dir, user_ans.r, user_ans.c);
            return false;
        }
        else {
            printf("OK @ tc(%d), query(%d)\n", tc, q);
        }
#endif
    }
    return true;
}

int main()
{
    //freopen("test.txt", "r", stdin);
    int seed;
    scanf("%d", &seed);
    srand(seed);

    for (tc = 0; tc < 100; ++tc)
    {
        if (tc < 50) {
            if (tc < 10) { N = 10; P = 3; }
            else if (tc < 20) { N = 10; P = 1; }
            else if (tc < 30) { N = 40; P = 3; }
            else if (tc < 40) { N = 40; P = 1; }
            else { N = 80; P = 1; }
        }
        else {
            if (tc < 60) { N = 100; P = 3; }
            else if (tc < 70) { N = 150; P = 1; }
            else if (tc < 80) { N = 150; P = 2; }
            else if (tc < 90) { N = MAX_N; P = 2; }
            else { N = MAX_N; P = 1; }
        }

        M = N / 2;
        Q = N;

        printf("%d\n", run());
    }

    return 0;
}

#define MAX_N 200 // 10 <= N <= 200
#define MAX_HASH 600011
#define _WALL 2
#define GOFORWARD 0
#define TURNRIGHT 1
#define NULL 0

enum DIR { UP, RIGHT, DOWN, LEFT, MAX_DIR };

int dR[MAX_DIR] = { 1, 1, -1, -1 };
int dC[MAX_DIR] = { 1, -1, -1, 1 };

struct POS {
    unsigned char r, c;
    unsigned char dir;
};

struct NODE {
    NODE *prev[MAX_DIR];
    NODE *next[MAX_DIR];
    unsigned int hash[MAX_DIR];
    unsigned char r, c;
};
NODE data[MAX_N][MAX_N];
NODE *h[MAX_DIR][MAX_HASH];
unsigned int used[MAX_DIR][MAX_N * MAX_N];
int used_cnt[MAX_DIR];
int _map[MAX_N][MAX_N];

extern void scan(int image[4][4]);
extern bool control(int cmd);

///////////////////////////////////////////////////////////////////////

#define ADD_HASH(dir) do { \
    node = &data[row][col]; \
    node->hash[dir] = hash; \
    H = hash % MAX_HASH; \
    node->next[dir] = h[dir][H]; \
    if (h[dir][H]) h[dir][H]->prev[dir] = node; \
    else used[dir][used_cnt[dir]++] = H; \
    h[dir][H] = node; \
} while(0) 

///////////////////////////////////////////////////////////////////////


// init은 map 크기와 map안에 들어갈 값(0, 1, 9)이 주어집니다.
// 각각의 방향에 대해 hash 를 만들어둠
void init(int n, const int map[MAX_N][MAX_N])
{
    static int test_case = 0;

    if (test_case == 0)
    {
        for (register int r = 0; r < MAX_N; ++r) {
            for (register int c = 0; c < MAX_N; ++c) {
                data[r][c].r = r;
                data[r][c].c = c;
            }
        }
        ++test_case;
    }

    for (register int i = 0; i < MAX_DIR; ++i) {
        for (register int j = 0; j < used_cnt[i]; ++j) {
            h[i][used[i][j]] = NULL;
        }
        used_cnt[i] = 0;
    }

    for (register int i = 0; i < n; ++i) {
        for (register int j = 0; j < n; ++j) {
            _map[i][j] = map[i][j] % 7;  // 9 --> 2 로 변환
        }
    }

    // hash update
    register unsigned int hash;
    register NODE *node;
    int row, col, r, c;
    int H;

    // hash for UP
    int end = n - 4;  // ((0,0) ~ (N-2, N-2) 의 hash 업데이트)
    for (row = 0; row <= end; ++row)
    {
        hash = 0;

        col = 0;
        int end_c = col + 4;
        int end_r = row + 4;

        for (c = col; c < end_c; ++c)
        {
            for (r = row; r < end_r; ++r)
            {
                hash = (hash << 2) | _map[r][c];
            }
        }
        ADD_HASH(UP);


        for (col = 1; col <= end; ++col)
        {
            c = col + 3;
            for (r = row; r < end_r; ++r)
            {
                hash = (hash << 2) | _map[r][c];
            }
            ADD_HASH(UP);
        }
    }


    // hash for DOWN
    end = 3;
    for (row = n - 1; row >= end; --row)
    {
        hash = 0;

        col = n - 1;
        int end_c = col - 4;
        int end_r = row - 4;

        for (c = col; c > end_c; --c)
        {
            for (r = row; r > end_r; --r)
            {
                hash = (hash << 2) | _map[r][c];
            }
        }
        ADD_HASH(DOWN);

        for (col = n - 2; col >= end; --col)
        {
            c = col - 3;
            for (r = row; r > end_r; --r)
            {
                hash = (hash << 2) | _map[r][c];
            }
            ADD_HASH(DOWN);
        }
    }


    // hash for LEFT
    end = n - 4;
    for (col = 0; col <= end; ++col)
    {
        hash = 0;

        row = n - 1;
        int end_c = col + 4;
        int end_r = row - 4;

        for (r = row; r > end_r; --r)
        {
            for (c = col; c < end_c; ++c)
            {
                hash = (hash << 2) | _map[r][c];
            }
        }
        ADD_HASH(LEFT);

        for (row = n - 2; row >= 3; --row)
        {
            r = row - 3;
            for (c = col; c < end_c; ++c)
            {
                hash = (hash << 2) | _map[r][c];
            }
            ADD_HASH(LEFT);
        }
    }


    // hash for RIGHT
    end = 3;
    for (col = n - 1; col >= end; --col)
    {
        hash = 0;

        row = 0;
        int end_c = col - 4;
        int end_r = row + 4;

        for (r = row; r < end_r; ++r)
        {
            for (c = col; c > end_c; --c)
            {
                hash = (hash << 2) | _map[r][c];
            }
        }
        ADD_HASH(RIGHT);

        for (row = 1; row <= n - 4; ++row)
        {
            r = row + 3;
            for (c = col; c > end_c; --c)
            {
                hash = (hash << 2) | _map[r][c];
            }
            ADD_HASH(RIGHT);
        }
    }
}

// find_where는 로봇의 위치를 찾아서 row, col, direction을 저장해서 main에 리턴해주는 함수입니다
POS find_where()
{
    POS ret;
    int image[4][4];
    int t_r_cnt = 0;
    bool inUse = false;

    while (1)
    {
        scan(image);

        // 벽9를 2로 변환
        for (register int i = 0; i < 4; ++i) {
            for (register int j = 0; j < 4; ++j) {
                if (image[i][j] > _WALL) image[i][j] = _WALL;
            }
        }

        // calc hash
        unsigned int hash, hash2;
        {
            register unsigned int h = 0;
            for (int c = 0; c < 4; ++c) {
                for (register int r = 0; r < 4; ++r) {
                    h = (h << 2) | image[r][c];
                }
            }
            hash = h;
            hash2 = h % MAX_HASH;
        }

        // 위의 hash, hash2 값을 가지고?
        int hit_cnt = 0;
        bool goOn = true;
        for (register int i = 0; i < MAX_DIR && goOn; ++i)
        {
            register NODE *node = h[i][hash2];
            while (node)
            {
                if (hash == node->hash[i]) {
                    if (++hit_cnt == 1) {
                        ret.dir = i;
                        ret.r = node->r + dR[i];
                        ret.c = node->c + dC[i];
                    }
                    else {
                        goOn = false;
                        break;
                    }
                }

                node = node->next[i];
            }
        }

        if (hit_cnt == 1) return ret;
#if 0
        while (!control(GOFORWARD)) control(TURNRIGHT);
#else
        if (t_r_cnt > 4) {
            if (image[1][0] != _WALL && image[2][0] != _WALL) {  // LEFT

                if (image[1][3] != _WALL && image[2][3] != _WALL) { // RIGHT
                    if (inUse ^= 1) control(TURNRIGHT);
                }
                else {
                    control(TURNRIGHT);
                    control(TURNRIGHT);
                    control(TURNRIGHT);
                }
                t_r_cnt = 0;
            }
        }

        while (!control(GOFORWARD)) {
            control(TURNRIGHT);
            ++t_r_cnt;
        }
#endif
    }
}

 

- 신기함
- main, user
- 원하는 결과값을 찾아내기
- hash 를 사용하고
- 그리고 원하는 값을 찾아냄
- 어떻게 하면 편리하게 찾을 수 있을까
- 해쉬 사용 법 익히기