[1913] 달팽이

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

1913번: 달팽이

<문제>

(n/2, n/2)에서 시작하는 경우에는 위->오른쪽->아래->왼쪽->위...처럼 방향이 돌아가며

방향이 바뀌지 않고, 방향을 유지하며 진행하는 횟수는 { 1 1 2 2 3 3 4 4 ...}의 순열을 따름을 이용해 구현하면 된다.

 

반대로 (0, 0)에서 시작하는 경우에는, 바로 위 방법에서 방향을 반대로 바꾸고

일단 진행하다, 맵을 벗어나거나 이미 탐색한 공간이 등장한 경우에는 방향을 바꾸어주면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, tar, a[1003][1003], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> tar;
    int i, j, y = 0, x = 0, key = 1, S = n * n;
    for (i = 0; i < S; i++) {
        a[y][x] = S - i;
        y = y + dy[key];
        x = x + dx[key];
        if (y < 0 || x < 0 || y >= n || x >= n || a[y][x] != 0) {
            y -= dy[key];
            x -= dx[key];
            key--;
            if (key == -1) key = 3;
            y = y + dy[key];
            x = x + dx[key];
        }
    }
    pair<int, int> ans;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (a[i][j] == tar) ans = {i + 1, j + 1};
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }
    cout << ans.first << " " << ans.second;
    return 0;
}