/*
23290번: 마법사 상어와 복제
https://www.acmicpc.net/problem/23290
*/
#include<iostream>
#include<vector>
#define MAP_SIZE 4
using namespace std;
#define sync_off \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
int m;
int s;
// 4*4 격자칸에 / 8개 방향의 물고기가 몇 마리 들었는지 적재
vector<vector<vector<int>>> vMap(MAP_SIZE, vector<vector<int>>(MAP_SIZE, vector<int>(8, 0)));
//←, ↖, ↑, ↗, →, ↘, ↓, ↙
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
pair<int, int> sharkState;
void input()
{
cin >> m >> s;
for (int i = 0; i < m; i++)
{
int y, x, d;
cin >> y >> x >> d;
vMap[y - 1][x - 1][d - 1]++;
}
cin >> sharkState.first >> sharkState.second;
sharkState.first -= 1;
sharkState.second -= 1;
}
void resultPrint()
{
int cnt=0;
for(int i=0;i<MAP_SIZE;i++)
{
for(int j=0;j<MAP_SIZE;j++)
{
for(int d=0;d<8;d++)
{
cnt += vMap[i][j][d];
}
}
}
cout<<cnt;
}
bool isEnableMove(int y, int x, int n, int m)
{
if (y < 0 || y >= n || x < 0 || x >= m)
return false;
else
return true;
}
// 1. 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
vector<vector<vector<int>>> step1()
{
return vMap;
}
// 2. 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다.
// 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다.
// 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
void step2(vector<vector<int>> &smellZone)
{
vector<vector<vector<int>>> temp(MAP_SIZE, vector<vector<int>>(MAP_SIZE, vector<int>(8, 0)));
for(int i=0;i<MAP_SIZE;i++)
{
for(int j=0;j<MAP_SIZE;j++)
{
for(int d=0;d<8;d++)
{
int fishCnt = vMap[i][j][d];
if (fishCnt == 0)
continue;
bool isMoveEnd = false;
for (int nd = d + 8; nd > d; nd--)
{
int ny = i + dy[(nd) % 8];
int nx = j + dx[(nd) % 8];
if (ny == sharkState.first && nx == sharkState.second)
continue;
if (!isEnableMove(ny, nx, MAP_SIZE, MAP_SIZE))
continue;
if (smellZone[ny][nx] != -1)
continue;
temp[ny][nx][(nd) % 8] += fishCnt;
isMoveEnd = true;
break;
}
if(!isMoveEnd)
temp[i][j][d] += fishCnt;
}
}
}
vMap = temp;
}
struct MoveSharkInfo
{
int score;
int eatFishCnt;
};
// note : 상어의 이동 방법 중 사전 순으로 가장 앞서는 방법을 찾으려면 먼저, 방향을 정수로 변환해야 한다. 상은 1, 좌는 2, 하는 3, 우는 4로 변환한다.
// 변환을 모두 마쳤으면, 수를 이어 붙여 정수로 하나 만든다. 두 방법 A와 B가 있고, 각각을 정수로 변환한 값을 a와 b라고 하자. a < b를 만족하면 A가 B보다 사전 순으로 앞선 것이다.
void findDfs(pair<int,int> _sharkPos, int depth, vector<vector<int>> &tfishCnt, MoveSharkInfo &vest, MoveSharkInfo cur)
{
if(depth==3)
{
if (vest.eatFishCnt < cur.eatFishCnt)
{
vest = cur;
}
else if (vest.eatFishCnt == cur.eatFishCnt)
{
if (vest.score > cur.score)
vest.score = cur.score;
}
return;
}
// 상, 하, 좌, 우
int dIndex[4] = {2, 0, 6, 4};
for (int i = 0; i < 4; i++)
{
int ny = _sharkPos.first + dy[dIndex[i]];
int nx = _sharkPos.second + dx[dIndex[i]];
if (!isEnableMove(ny, nx, MAP_SIZE, MAP_SIZE))
continue;
int nScore = (cur.score * 10) + (i + 1);
int nEatFishCnt = cur.eatFishCnt + tfishCnt[ny][nx];
int saveFishCnt = tfishCnt[ny][nx];
tfishCnt[ny][nx] = 0;
findDfs({ny, nx}, depth + 1, tfishCnt, vest, {nScore, nEatFishCnt});
tfishCnt[ny][nx] = saveFishCnt;
}
}
// 3. 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다.
// 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다.
// 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
void step3(vector<vector<int>> &smellZone, int cSmellCnt)
{
MoveSharkInfo vest = {999, 0};
vector<vector<int>> fishCnt(MAP_SIZE, vector<int>(MAP_SIZE, 0));
for(int i=0;i<MAP_SIZE;i++)
{
for(int j=0;j<MAP_SIZE;j++)
{
for (int k = 0; k < 8; k++)
{
fishCnt[i][j] += vMap[i][j][k];
}
}
}
findDfs(sharkState, 0, fishCnt, vest, {0, 0});
int score = vest.score;
int moveDir[3];
int dIndex[4] = {2, 0, 6, 4};
for(int i=0;i<3;i++)
{
int c = score % 10;
moveDir[2 - i] = dIndex[c - 1];
score /= 10;
}
int y,x;
y=sharkState.first;
x=sharkState.second;
for (int i = 0; i < 3; i++)
{
y += dy[moveDir[i]];
x += dx[moveDir[i]];
bool isSmellOn = false;
for (int j = 0; j < 8; j++)
{
if(vMap[y][x][j]!=0)
{
isSmellOn = true;
vMap[y][x][j] = 0;
}
if (isSmellOn)
{
smellZone[y][x] = cSmellCnt;
}
}
}
sharkState = {y, x};
}
// 4. 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
void step4(vector<vector<int>> &smellZone, int cSmellCnt)
{
int rSmellCnt = (cSmellCnt + 1) % 3;
for (int i = 0; i < MAP_SIZE; i++)
{
for (int j = 0; j < MAP_SIZE; j++)
{
// que 써도 될거같긴 한데 map size가 4밖에 안되니까 일단 이렇게 전부 찾는다.
if (smellZone[i][j] == rSmellCnt)
smellZone[i][j] = -1;
}
}
}
// 5. 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.
void step5(vector<vector<vector<int>>> &_map)
{
for (int i = 0; i < MAP_SIZE; i++)
{
for (int j = 0; j < MAP_SIZE; j++)
{
for (int k = 0; k < 8; k++)
{
vMap[i][j][k] += _map[i][j][k];
}
}
}
}
void printMap()
{
cout<<"\n"<<sharkState.first<<" "<<sharkState.second<<"\n";
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
for(int k=0;k<8;k++)
{
if(vMap[i][j][k]!=0)
cout<<i<<" "<<j<<" "<<k<<"\n";
}
}
}
}
void solve()
{
vector<vector<int>> smellZone(MAP_SIZE, vector<int>(MAP_SIZE, -1));
for (int i = 0; i < s; i++)
{
vector<vector<vector<int>>> copy_map;
int cSmellCnt = i % 3;
copy_map = step1();
step2(smellZone);
step3(smellZone, cSmellCnt);
step4(smellZone, cSmellCnt);
step5(copy_map);
// printMap();
}
}
int main()
{
sync_off;
input();
solve();
resultPrint();
return 0;
}
카테고리 없음