19236(청소년 상어)
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <unordered_set>
#include <math.h>
#include <utility>
#include <tuple>
using namespace std;
int dx[] = { 0,-1,-1,-1,0,1,1,1}; // 반시계 방향으로 정의
int dy[] = { -1,-1, 0 ,1,1,1,0,-1 };
int answer = 0;
typedef struct s_fish {
int d; //direction (0~ 7);
int number; // 0 is dead, else is alive , -1 is shark
}t_fish;
typedef struct s_shark {
int y;
int x;
int sum_number;
int d;
}t_shark;
void move_fish(t_fish map[4][4], int y, int x, vector<tuple<int, int, int > > &tp) //기존 백터 의포인터를 받는다.(참조자 연산)
{
for (int i = 0; i < 8; i++)
{
int d = map[y][x].d + i; // 현재 방향에서 8방향 증가
if (d >= 8) // 예외처리
d -= 8;
int ny = y + dy[d];
int nx = x + dx[d];
if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4)
{
if (map[ny][nx].number != -1) // 상어가 없으면
{
t_fish temp = map[ny][nx];
map[ny][nx] = map[y][x]; // 스왑
map[ny][nx].d = d; // 방향 설정
map[y][x] = temp;
if (temp.number > 0)
{
get<1>(tp[temp.number - 1]) = y;
get<2>(tp[temp.number - 1]) = x;
}
get<1>(tp[map[ny][nx].number - 1]) = ny;
get<2>(tp[map[ny][nx].number - 1]) = nx;
return;
}
}
}
}
void next_step(t_fish map[4][4], t_shark shark, vector<tuple<int, int, int > > tp) // 새로운 백터를 받는 복사 생성자가 호출된다
{
shark.sum_number += map[shark.y][shark.x].number;
map[shark.y][shark.x].number = -1;
shark.d = map[shark.y][shark.x].d;
for (auto elem : tp) //순서가 적은거 부터 움직이자
{
int i = get<1>(elem);
int j = get<2>(elem);
if (get<0>(elem) > 0)
if (map[i][j].number > 0)//상어자리가 아니고 빈 공간이 아니면
move_fish(map, i, j, tp);
}
// move shark
int ny = shark.y;
int nx = shark.x;
int bx = shark.x; // 기존위치 백업
int by = shark.y;
for (int i = 0; i < 3; i++) //4x4이기 때문에 최대 3번 움직인다.
{
ny += dy[shark.d];
nx += dx[shark.d];
if (ny >= 0 && ny < 4 && nx >= 0 && nx < 4)
{
if (map[ny][nx].number > 0) // 물고기가 있으면
{
t_fish new_map[4][4];
for(int j = 0 ; j < 4; j++)
memcpy(new_map[j], map[j], sizeof(map[j])); // 새로운 맵 복사
new_map[by][bx].number = 0; //자리번호 0으로 초기화
get<0>(tp[map[ny][nx].number - 1]) = 0; // 죽음 표시
shark.y = ny;
shark.x = nx;
next_step(new_map, shark, tp);
get<0>(tp[map[ny][nx].number - 1]) = map[ny][nx].number; // 재귀가 끝났으니 다시 살린다.
}
}
}
answer = max(answer, shark.sum_number);
}
int main(void)
{
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
freopen("input.txt", "r", stdin);
vector<tuple<int, int, int > > tp;// 번호 낮은거부터 하기위한 벡터
t_fish origin_map[4][4];
for (int i = 0; i < 4;i++)
{
for (int j = 0; j < 4; j++)
{
t_fish fish;
cin >> fish.number;
cin >> fish.d;
fish.d -= 1; //because of using from 0
origin_map[i][j] = fish;
tp.push_back(make_tuple(fish.number, i, j));
}
}
t_shark shark;
shark.x = 0;
shark.y = 0;
shark.d = 0;
shark.sum_number = 0;
sort(tp.begin(), tp.end());
get<0>(tp[origin_map[0][0].number - 1]) = 0; // 죽음 표시
next_step(origin_map, shark, tp);
cout << answer;
return (0);
}
고찰
문제는 길지만 이해하고 나면 간단하다.
구현 과정에 있어서 tuple을 처음 써본지라 시간이 오래걸렸다.
상어가 이동할 때마다 새로운 map배열을 만들어서 재귀 시켜 주었다.
코드를 더 깔끔하게 짤 수 있을 것 같은데 뭔가 더러워졌다. 아쉬움이 남는다.