[1952] 달팽이2

달팽이2 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	478	260	216	56.397%

문제

M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.

ㅇ

위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.

ㅇ	→	↘
↗	↘	↓
↑	↓	↓
↑	끝	↓
↖	←	↙

위의 표는 선을 그려 나간 모양을 나타낸 것이다. (선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까?

입력

첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2≤M, N≤100)

출력

첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다.

예제 입력 

5 3

예제 출력 

5

힌트

예전에는 굉장히 어렵게 생각해서 실패했던 문제인데...

지금 푸니까 왜 이렇게 쉬울까요..

방향이 꺾이는 경우는 딱 두가지입니다.

1. 맵 밖으로 나간다.

2. 방문했던 곳이다.

예전엔 2번이 어려웠는데... 그냥 맵을 만들어서 방문표시하면 끝인데.. 왜어렵게 생각했을까요...

와일문 탈출조건은 

만약 방향을 꺾어서 이동했음에도 불구하고 방문한 곳이라면 모든 맵을 다 방문한 것입니다!!

그러므로 탈출하고 마지막에 꺾인 부분은 제외해야하므로 1을 뺴준것이 정답입니다.!

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cstdio>
#include <stack>
#define MAX_SIZE 100
#define MOD 1000000009
#define ull unsigned long long
#define ll long long
 
using namespace std;
 
 
bool visit[MAX_SIZE][MAX_SIZE];
int m, n;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
//3 -> 1, 1 -> 2, 2 -> 0, 0 -> 3
//오 -> 아, 아 -> 왼, 왼 -> 위 , 위 -> 오
 
int set_direct(int d)
{
    if(d == 3 || d == 2) return (d + 2) % 4;
    else return 3 - d;
}
 
 
int main()
{
 
    scanf("%d %d", &m, &n);
 
    int x=0, y=0;
    int d = 3;
    int ret = 0;
 
    while(1)
    {
        if(visit[x][y] == 1) break;
 
        visit[x][y] = 1;
 
        int nx = x + dx[d];
        int ny = y + dy[d];
 
 
        if(visit[nx][ny] == 1 || nx < 0 || ny < 0 || nx >= m || ny >= n)
        {
            d = set_direct(d);
            nx = x + dx[d];
            ny = y + dy[d];
            ret++;
        }
 
        x = nx;
        y = ny;
    }
 
    printf("%d\n", ret - 1);
 
    return 0;
}