#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
pair<pair<int,int>,int> board[105][105];
pair<pair<int,int>,int> tmp[105][105];
queue<pair<int,int>> shark;
int R,C,M,ans;
int reverseDir(int n){
if(n == 0) return 1;
if(n == 1) return 0;
if(n == 2) return 3;
if(n == 3) return 2;
return 5;
}
bool checkPos(int y, int x){
if(x<0 or y<0 or x>=C or y>=R) return false;
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> R >> C >> M;
for(int i=0;i<M;i++)
{
int r,c,s,d,z;
cin >> r >> c >> s >> d >> z;
board[r-1][c-1] = {{s,d-1},z};
shark.push({r-1,c-1});
}
for(int cur_pos=0;cur_pos<C;cur_pos++)
{
pair<int,int> deletPos={1e9,1e9};
for(int j=0;j<R;j++)
if(board[j][cur_pos].second != 0)
{
ans += board[j][cur_pos].second;
board[j][cur_pos] = {{0,0},0};
deletPos = {j,cur_pos};
break;
}
int len = shark.size();
while(len--)
{
auto cur = shark.front(); shark.pop();
if(deletPos.first == cur.first and deletPos.second == cur.second) continue;
int speed = board[cur.first][cur.second].first.first;
int dir = board[cur.first][cur.second].first.second;
int ny=cur.first, nx=cur.second;
if(dir == 0 or dir == 1){
speed = speed%(R*2-2);
}else{
speed = speed%(C*2-2);
}
while(speed > 0)
{
speed--;
ny = ny + dy[dir];
nx = nx + dx[dir];
if(!checkPos(ny,nx)){
dir = reverseDir(dir);
board[cur.first][cur.second].first.second = dir;
ny = ny + dy[dir] + dy[dir];
nx = nx + dx[dir] + dx[dir];
}
}
int curSize = tmp[ny][nx].second;
int nextSize = board[cur.first][cur.second].second;
if(curSize < nextSize)
tmp[ny][nx] = board[cur.first][cur.second];
}
for(int a=0;a<R;a++)
{
for(int b=0;b<C;b++)
{
board[a][b] = tmp[a][b];
tmp[a][b] = {{0,0},0};
if(board[a][b].second != 0)
shark.push({a,b});
}
}
}
cout << ans;
return 0;
}
- 핵심
: 시간복잡도
줄이기
1) 이동해야하는 상어
를 queue
를 통해서 관리
하였고, size
를 통해 이번 차례 상어
까지만 수행함
2) speed
에 따라 상어가 움직이는 과정
에서 speed
가 최대 1,000
이라는 숫자를 가져서 시간초과
가 날 확률이 크다
--> speed
를 방향
에 따라 R과 C로 나눠서
제자리로 오는 경우
만큼 줄일 수 있음