#include <iostream>
#include <vector>
#include <cstring> // memset

using namespace std;

int N, M;
int A[50][50];

vector<int> v; // 재배열할 구슬들 저장

int d, s; // 방향, 거리
int sharkX, sharkY;

// 블리자드 마법 4가지 방향 ↑, ↓, ←, →
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

// 좌표평면 도는 방향 좌 하 우 상
int ddx[4] = {-1, 0, 1, 0};
int ddy[4] = {0, 1, 0, -1};

int score = 0;

void move(){
  // 구슬 넣어줄 벡터 초기화
  v.clear();

  int distance = 1;
  int nx = sharkX; int ny = sharkY;
  d = 0; // 왼쪽 방향부터 좌표 평면 돌기 시작
  int cnt = 0; int maxCnt = N * N - 1; // 격자 모든 칸 돌기

  // 격자 끝까지 탐색
  // 벡터를 이용해서 빈칸이 아닌 경우만 벡터에 저장해서 폭발 후 재배열 시켜줄 것임.
  // 13퍼 에러는 이거 에러
  while(1){
    for(int i = 0; i < 2; i++){
      for(int j = 0; j < distance; j++){
        nx += ddx[d];
        ny += ddy[d];

        cnt++;

        if(nx < 0 || ny < 0 || nx >= N || ny >= N){
          continue;
        }

        if(A[ny][nx] > 0){
          v.push_back(A[ny][nx]);
        }
      }
      if(cnt >= maxCnt){
        break;
      }
      d = (d + 1) % 4; // 다음 방향으로 이동
    }
    if(cnt >= maxCnt){
      break;
    }
    distance++; // 2번마다 길이 늘어남
  }
}

void explore(){
  // 벡터에 구슬 저장되어 있기 때문에 4개 이상 연속하는 구슬 찾기 쉬움.
  bool flag = true; // 폭발한 후에도 또 폭발할 것 있으면 폭발해야함

  while(flag){
    flag = false; // 아직 폭발한 것 없음
    vector<int> tmp; // 벡터 내의 구슬을 터뜨리지 말고 임시 배열에 안 터진 구슬을 저장시키기

    if(v.size() == 0){
      return;
    }
    
    for(int i = 0; i < v.size(); i++){
      int next = i; // 바로 다음 인덱스 x out of bound

      if(v[i] != v[next]){
        tmp.push_back(v[i]);
      } else {
        // 범위 안에서 같은 경우 모두 탐색
        while(v[i] == v[next] && next < v.size()){
          next++;
        }

        // 4개 이하인 경우 (next++ 라서 next - i + 1 아님)
        if(next - i < 4){
          for(int j = i; j < next; j++){
            tmp.push_back(v[j]); // 안터진 구슬 저장
          }
        } else {
          // 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)
          score += v[i] * (next - i);
          flag = true; // 구슬 폭발함
        }
      }
      i = --next; // idx 업데이트
    }
    v = tmp; // 임시 배열 값 구슬 값으로 재저장 copy 그냥 이렇게
  }
}

void change(){
  vector<int> tmp;

  if(v.size() == 0){
    return;
  }

  for(int i = 0; i < v.size(); i++){
    int next = i; // 다음 인덱스 구할 것

    while(v[i] == v[next] && next < v.size()){
      next++;
    }
    // 개수
    tmp.push_back(next - i);
    // 그룹을 이루고 있는 구슬의 번호
    tmp.push_back(v[i]);

    // 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다.
    // >=
    if(tmp.size() >= N * N){
      while(tmp.size() >= N * N){
        tmp.pop_back();
      }
    }
    i = --next;
  }
  v = tmp;
}

void mapSet(){
  memset(A, 0, sizeof(A));
  int nx = sharkX; int ny = sharkY;
  int d = 0; // 맵도는 방향부터 시작
  int distance = 1;
  int idx = 0; // vector idx

  if(v.size() == 0){
    return;
  }

  while(1){
    for(int i = 0; i < 2; i++){
      for(int j = 0; j < distance; j++){
        nx += ddx[d];
        ny += ddy[d];

        if(nx < 0 || ny < 0 || nx >= N || ny > N){
          continue;
        }

        A[ny][nx] = v[idx];
        idx++;

        if(idx == v.size()){
          return;
        }
      }
      d = (d + 1) % 4;
    }
    distance++;
  }
}

int main(){
  scanf("%d %d", &N, &M);

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      scanf("%d", &A[i][j]);
    }
  }

  // 상어 위치 저장 맵 (0, 0)부터 시작
  sharkX = N / 2; sharkY = N / 2;

  for(int i = 0; i < M; i++){
    scanf("%d %d", &d, &s);
    d--; // 방향 인덱스 0부터 시작하기 때문에

    // 구슬 파괴 - 블리자드 마법
    int nx = sharkX; int ny = sharkY;
    for(int j = 0; j < s; j++){
      nx += dx[d];
      ny += dy[d];
      if(nx < 0 || ny < 0 || nx >= N || ny >= N){
        continue;
      }
      A[ny][nx] = 0;
    }

    // 구슬 이동
    move();
    // 구슬 폭발
    explore();
    // 구슬 변화
    change();
    // 벡터에 저장된 값들 맵에 재저장
    mapSet();
  }

  printf("%d", score);

  return 0;
}

진짜 너무 괴로웠음. 아 조금만 더 하면 될 것 같은데... 하면서 했는데
너무 힘들더라고...

문제 풀이.

맵(2차원 배열)과 구슬을 저장하는 벡터(1차원 배열)을 동시에 사용했다.
이러한 방법이 폭발하는 구슬 탐색에도 훨씬 쉽고 이해하기가 빨라 인터넷 뒤져보고 이러한 방식을 차용했음.

1. 전역변수

// 블리자드 마법 4가지 방향 ↑, ↓, ←, →
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

// 좌표평면 도는 방향 좌 하 우 상
int ddx[4] = {-1, 0, 1, 0};
int ddy[4] = {0, 1, 0, -1};

블리자드 마법을 사용할때 탐색하는 방향과 맵에서 좌표평면을 도는 방향은 다른 순서의 규칙을 가진다.
따라서 따로 계산을 할 수 있도록 배열을 만들어주었다.

2. 구슬 파괴 - 블리자드 마법

// 상어 위치 저장 맵 (0, 0)부터 시작
  sharkX = N / 2; sharkY = N / 2;

맵을 (0,0) 부터 채워넣었기 때문에 상어의 위치는 N/2가 된다.
(1,1)부터 시작하는 경우에는 (N+1)/2가 된다.

ex) N = 3일때 맵이 (0,0)부터 시작하면 중간지점은 (1,1)
(1,1)부터 시작하면 중간지점은 (2,2)가 된다.

for(int i = 0; i < M; i++){
    scanf("%d %d", &d, &s);
    d--; // 방향 인덱스 0부터 시작하기 때문에

    // 구슬 파괴 - 블리자드 마법
    int nx = sharkX; int ny = sharkY;
    for(int j = 0; j < s; j++){
      nx += dx[d];
      ny += dy[d];
      if(nx < 0 || ny < 0 || nx >= N || ny >= N){
        continue;
      }
      A[ny][nx] = 0;
    }

구슬 파괴는 식이 간단하기에 따로 함수로 뺴지 않고 작성하였다.

dx, dy로 방향으로 구슬을 0으로 초기화시켜주면 된다. (파괴)

3. 구슬 폭발

void explore(){
  // 벡터에 구슬 저장되어 있기 때문에 4개 이상 연속하는 구슬 찾기 쉬움.
  bool flag = true; // 폭발한 후에도 또 폭발할 것 있으면 폭발해야함

  while(flag){
    flag = false; // 아직 폭발한 것 없음
    vector<int> tmp; // 벡터 내의 구슬을 터뜨리지 말고 임시 배열에 안 터진 구슬을 저장시키기

    if(v.size() == 0){
      return;
    }
    
    for(int i = 0; i < v.size(); i++){
      int next = i; // 바로 다음 인덱스 x out of bound

      if(v[i] != v[next]){
        tmp.push_back(v[i]);
      } else {
        // 범위 안에서 같은 경우 모두 탐색
        while(v[i] == v[next] && next < v.size()){
          next++;
        }

        // 4개 이하인 경우 (next++ 라서 next - i + 1 아님)
        if(next - i < 4){
          for(int j = i; j < next; j++){
            tmp.push_back(v[j]); // 안터진 구슬 저장
          }
        } else {
          // 1×(폭발한 1번 구슬의 개수) + 2×(폭발한 2번 구슬의 개수) + 3×(폭발한 3번 구슬의 개수)
          score += v[i] * (next - i);
          flag = true; // 구슬 폭발함
        }
      }
      i = --next; // idx 업데이트
    }
    v = tmp; // 임시 배열 값 구슬 값으로 재저장 copy 그냥 이렇게
  }
}

구슬은 연쇄적으로 계속 4개 이상이 모이면 폭발하기 때문에
모든 구슬이 폭발하지 않을 때 까지 while문을 돌면서 탐색해 구슬을 폭발시켜준다.

그리고 주의할 것이,
구슬을 저장시킨 v 벡터가 비어있는지를 체크해줘야한다.
체크 안해주면 out of Bound 에러 생김 ㅋㅋ ㅜㅜ 눈물난다.

연속된 수 찾기

벡터는 일차원 배열이기 때문에 일차원 배열에서 연속된 것을 찾는 알고리즘을 사용하면 된다.

다음 인덱스를 가리키는 int next 는 초깃값을 i + 1로 두면 안된다.
out of bound 에러가 발생한다.
만약 i = n - 1일 경우 next = n을 가리키기 때문에 메모리 범위 너머의 값을 접근하려고 하기 때문이다.

while문을 사용해서 next가 범위 내 일때, 값이 같은 것들을 순회해서 구해주면 된다.
next와 현재 인덱스(i)의 차이를 이용해 연속되는 구슬의 개수를 구하고 그에 따라 계산을 해주면 된다.
next는 i 순회를 한 것과 같으므로 현재 인덱스를 next 값으로 갱신시켜주면 된다.

벡터 바꿔치기

벡터 복사라기에는 백터 바꿔치기가 적절한 표현일 것 같음.
뭐 vector copy 이런거 안 쓰고 그냥 v = tmp 이런식으로 가리키는 것만 바꿔주면 된다.
깔끔! 계속 구슬 저장 값을 갱신시켜주는 것이다.

그리고 아직 구슬을 변화시켜야 하는 단계가 남아있으므로 아직 기존 맵에 바뀐 구슬 정보를 넣어주지 않는다.
그냥 구슬 순서가 담긴 벡터를 이용하면 됨.

4. 구슬 변화

void change(){
  vector<int> tmp;

  if(v.size() == 0){
    return;
  }

  for(int i = 0; i < v.size(); i++){
    int next = i; // 다음 인덱스 구할 것

    while(v[i] == v[next] && next < v.size()){
      next++;
    }
    // 개수
    tmp.push_back(next - i);
    // 그룹을 이루고 있는 구슬의 번호
    tmp.push_back(v[i]);

    // 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다.
    // >=
    if(tmp.size() >= N * N){
      while(tmp.size() >= N * N){
        tmp.pop_back();
      }
    }
    i = --next;
  }
  v = tmp;
}

여기도 마찬가지로 구슬이 있는지 여부를 체크해줘야한다.
구슬이 이미 다 터져버려서 체크할 상황이 안 생길수도 있음.
체크 안해주면 out of bound 에러 생김...

일차원 배열 탐색

여기도 마찬가지로 연속되는 수를 세어주고 (개수, 구슬 번호)순으로 벡터에 넣어주면 된다.
이때 구슬의 수가 맵보다 많아질 수 있다.
그런 경우 체크해서(N x N개보다 크거나 같을 경우 = 상어가 있어서 구슬은 최대 N x N -1개)
벡터에서 pop 시켜준다.

벡터에서도 pop을 사용할 수 있음. 그렇게 하면 뒤의 값 삭제 가능함!!

5. 맵에 구슬 위치 복원

void mapSet(){
  memset(A, 0, sizeof(A));
  int nx = sharkX; int ny = sharkY;
  int d = 0; // 맵도는 방향부터 시작
  int distance = 1;
  int idx = 0; // vector idx

  if(v.size() == 0){
    return;
  }

  while(1){
    for(int i = 0; i < 2; i++){
      for(int j = 0; j < distance; j++){
        nx += ddx[d];
        ny += ddy[d];

        if(nx < 0 || ny < 0 || nx >= N || ny > N){
          continue;
        }

        A[ny][nx] = v[idx];
        idx++;

        if(idx == v.size()){
          return;
        }
      }
      d = (d + 1) % 4;
    }
    distance++;
  }
}

여기가 은근 진짜 야마돌았던 부분이다.

while로 좌표평면 소용돌이 순회

while문을 돌면서 구슬을 모두 채울 때 까지 반복하는데
이 while문을 언제 멈출것인가 그게 은근히 메모리 초과를 발생시킨다.

처음에는 nx, ny 가 (0,0)에 다다르면 종료 이런식으로 했는데 안되더라.
왜 인지는 아직도 잘 모르겠음. 예제에서는 다 잘 되던데 아무튼...
14%인가에서 계속 오류가 난다면 이 범위가 문제일 수도 있다는 의미다.

혹시 시험에서도 이러한 문제가 나오면 실수할 수도 있으니까
while문에서 좌표로 멈추게 하는 것은 지양하는 것이 좋을 듯 하다.

사용 방법

그래서 사용한 방법은, 구슬 크기만큼 while문을 실행하는 것이다.
idx 변수를 이용해서 v.size()인 구슬 크기만큼 실행이 되면 반복문을 멈추게끔 하였다.
어쨌든, 구슬 값에 접근하기 위해서 idx 변수를 사용하기 때문에.

다른 방법

cnt를 사용해서 맵을 탐색할 수 있는 크기인 N * N - 1만큼 탐색하게 하던가
아니면 구슬 크기를 계속 cnt 변수를 사용해서 모든 구슬 더하기 빼기를 할 때마다 따로 세어서
그만큼 탐색해주는 사람도 있더라.

내 생각에는 위의 방법이 가장 간편하기도 하고 효율적인 것 같아서 저 방법을 사용했음.

맵 순회

맵을 순회하는 방법은
마법사 상어와 블리자드에서 사용한 방법을 이용했음.

while문을 사용하고, 방향을 바꿔가며 distance만큼 이동한다. 2번마다 distance는 1이 증가한다.
이렇게 순회하면서 벡터에 있는 구슬 값을 채워주면 됨.

아무튼 이게 전부다.
꽤 간단함. 벡터를 사용하겠다는 생각을 해냈으면 말이지...
1차원 벡터 순회는 정말 많이 해봤으니까.

주석 없는 코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, M;
int A[50][50];

vector<int> v;

int d, s;
int sharkX, sharkY;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int ddx[4] = {-1, 0, 1, 0};
int ddy[4] = {0, 1, 0, -1};

int score = 0;

void move(){
  v.clear();

  int distance = 1;
  int nx = sharkX; int ny = sharkY;
  d = 0;
  int cnt = 0; int maxCnt = N * N - 1;

  while(1){
    for(int i = 0; i < 2; i++){
      for(int j = 0; j < distance; j++){
        nx += ddx[d];
        ny += ddy[d];

        cnt++;

        if(nx < 0 || ny < 0 || nx >= N || ny >= N){
          continue;
        }

        if(A[ny][nx] > 0){
          v.push_back(A[ny][nx]);
        }
      }
      if(cnt >= maxCnt){
        break;
      }
      d = (d + 1) % 4;
    }
    if(cnt >= maxCnt){
      break;
    }
    distance++;
  }
}

void explore(){
  bool flag = true;

  while(flag){
    flag = false;
    vector<int> tmp;

    if(v.size() == 0){
      return;
    }
    
    for(int i = 0; i < v.size(); i++){
      int next = i;

      if(v[i] != v[next]){
        tmp.push_back(v[i]);
      } else {
        while(v[i] == v[next] && next < v.size()){
          next++;
        }

        if(next - i < 4){
          for(int j = i; j < next; j++){
            tmp.push_back(v[j]);
          }
        } else {
          score += v[i] * (next - i);
          flag = true;
        }
      }
      i = --next;
    }
    v = tmp;
  }
}

void change(){
  vector<int> tmp;

  if(v.size() == 0){
    return;
  }

  for(int i = 0; i < v.size(); i++){
    int next = i;

    while(v[i] == v[next] && next < v.size()){
      next++;
    }
    tmp.push_back(next - i);
    tmp.push_back(v[i]);

    if(tmp.size() >= N * N){
      while(tmp.size() >= N * N){
        tmp.pop_back();
      }
    }
    i = --next;
  }
  v = tmp;
}

void mapSet(){
  memset(A, 0, sizeof(A));
  int nx = sharkX; int ny = sharkY;
  int d = 0;
  int distance = 1;
  int idx = 0;

  if(v.size() == 0){
    return;
  }

  while(1){
    for(int i = 0; i < 2; i++){
      for(int j = 0; j < distance; j++){
        nx += ddx[d];
        ny += ddy[d];

        if(nx < 0 || ny < 0 || nx >= N || ny > N){
          continue;
        }

        A[ny][nx] = v[idx];
        idx++;

        if(idx == v.size()){
          return;
        }
      }
      d = (d + 1) % 4;
    }
    distance++;
  }
}

int main(){
  scanf("%d %d", &N, &M);

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      scanf("%d", &A[i][j]);
    }
  }

  sharkX = N / 2; sharkY = N / 2;

  for(int i = 0; i < M; i++){
    scanf("%d %d", &d, &s);
    d--;

    int nx = sharkX; int ny = sharkY;
    for(int j = 0; j < s; j++){
      nx += dx[d];
      ny += dy[d];
      if(nx < 0 || ny < 0 || nx >= N || ny >= N){
        continue;
      }
      A[ny][nx] = 0;
    }

    move();
    explore();
    change();
    mapSet();
  }

  printf("%d", score);

  return 0;
}