[BOJ-1913]달팽이

https://www.acmicpc.net/problem/1913

[접근방법]

시뮬레이션

주어진 조건에서 시작 위치를 

sr = int(n/2) + 1 ;

sc = int(n/2) + 1; 로 설정을 한 후 

크기가 1인 경우를 제외하고,

초기 값으로 1, 2 를 둔다. 

그리고 

가려는 진행방향에서 오른편에 값이 있다면 : 진행방향을 그대로 가서 값을 매긴다.

가려는 진행방향에서 오른편에 값이 없다면 : 진행방향을 오른편으로 움직인다. 그리고 값을 매긴다.

이후 순회를 하며, 원하는 위치의 값을 찾는다.

[C++ source code]

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
 
typedef vector<int> vi;
const int M = 1111;
const int dr[] = { -1,0,1,0 };
const int dc[] = { 0,1,0,-1 }; // U R D L
 
 
vi imap[M];
 
struct pos {
    int r, c;
    pos() {}
    pos(int ir, int ic) :r(ir), c(ic) {}
    void set_pos(int ir, int ic) {
        r = ir;
        c = ic;
    }
};
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int r = 1; r <= n; r++) {
        imap[r] = vi(n + 1, -1);
    }
    int want;
    scanf("%d", &want);
 
    // start node is row that int(n/2)+1 and col that int(n/2)
    int sr = int(n / 2) + 1;
    int sc = int(n / 2) + 1;
    imap[sr][sc] = 1;
    if (n == 1) {
        puts("1");
        puts("1 1");
        return 0;
    }
    imap[--sr][sc] = 2;
    int value = 2;
    int di = 0;
    while (1) {
        
        int ci = (di + 1) % 4;
        value++;
        if (imap[sr + dr[ci]][sc + dc[ci]] == -1) { // value is none
            imap[sr + dr[ci]][sc + dc[ci]] = value;
            di = ci;
        }
        else {
            imap[sr + dr[di]][sc + dc[di]] = value;
        }        
        sr += dr[di];
        sc += dc[di];
 
        if (value == n*n) break;
    }
 
    // operation end
    pos ans2;
    // answer1 ; map
    for (int r = 1; r <= n; r++) {
        for (int c = 1; c <= n; c++) {
            printf("%d ", imap[r][c]);
            if (imap[r][c] == want) {
                ans2.set_pos(r, c);
            }
        }
        puts("");
    }
    // answer2 ; want ~ row,col
    printf("%d %d\n", ans2.r, ans2.c);
 
    return 0;
}