딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/9657

#include <bits/stdc++.h>

using namespace std;

int N, dp[1003];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    dp[1] = 1;
    dp[2] = 0;
    dp[3] = 1;
    dp[4] = 1;

    cin >> N;

    for(int i=5; i<=1000; i++){
        dp[i] = max({!dp[i-4], !dp[i-3], !dp[i-1]});
    }

    if(dp[N]) cout << "SK";
    else cout << "CY";

    return 0;
}

https://www.acmicpc.net/problem/4883

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int num = 1;
    while (1) {
        int N;
        cin >> N;
        if (N == 0) break;

        int a, b, c;
        cin >> a >> b >> c;

        c = b + c;

        int dp[3], pre[3];
        cin >> dp[0] >> dp[1] >> dp[2];
        dp[0] += b;
        dp[1] = min({dp[0], b, c}) + dp[1];
        dp[2] = min({b, c, dp[1]}) + dp[2];

        for (int i = 1; i <= N - 2; i++) {
            int x, y, z;
            pre[0] = dp[0];
            pre[1] = dp[1];
            pre[2] = dp[2];

            cin >> x >> y >> z;

            dp[0] = x + min(pre[0], pre[1]);
            dp[1] = y + min({pre[0], pre[1], pre[2], dp[0]});
            dp[2] = z + min({pre[1], pre[2], dp[1]});

        }
        cout << num++ << ". " << dp[1] << '\n';
    }

    return 0;
}

https://www.acmicpc.net/problem/15486

#include <bits/stdc++.h>

using namespace std;
int N, day[1'500'003], preMax;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        int a, b;
        cin >> a >> b;

        day[i] = max(day[i], preMax);
        if (i + a <= N + 1) {
            day[i + a] = max(day[i + a], day[i] + b);
        }
        preMax = max(preMax, day[i]);
    }

    int ans = 0;
    for (int i = 1; i <= N + 1; i++) {
        ans = max(ans, day[i]);
    }

    cout << ans;
    return 0;
}

https://www.acmicpc.net/problem/23291

#include <bits/stdc++.h>

using namespace std;

int N, K, arr[101][101];

void addFish() {
    int min = INT_MAX;
    for (int i = 1; i <= N; i++) {
        if (arr[1][i] < min) min = arr[1][i];
    }

    for (int i = 1; i <= N; i++) {
        if (arr[1][i] == min) arr[1][i]++;
    }
}

void jumpBlock() {
    arr[2][2] = arr[1][1];
    arr[1][1] = 0;

    int stx = 2, sty = 2;
    int row = 2, col = 1;
    int cnt = 1;

    while (stx + sty <= N) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                arr[2 + j][sty + (row - i)] = arr[stx - i][sty - j];
                arr[stx - i][sty - j] = 0;
            }
        }

        sty += stx;
        if (cnt % 2 == 1) {
            col++;
        } else {
            row++;
            stx++;
        }

        cnt++;
    }
}


void fishControl() {
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    int tmp[101][101];
    memset(tmp, 0, sizeof(tmp));

    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j]) {
                int sum = 0;
                int minus = 0;

                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx <= 0 || nx > 100 || ny <= 0 || ny > N) continue;
                    if (arr[nx][ny] == 0)continue;

                    int diff = (arr[i][j] - arr[nx][ny]) / 5;

                    if (diff == 0) continue;
                    else if (diff > 0) {
                        minus += diff;
                    } else {
                        sum += abs(diff);
                    }
                }
                tmp[i][j] = arr[i][j] - minus + sum;
            }
        }
    }
    swap(tmp, arr);
}

void putDown() {
    int idx = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= 100; j++) {
            if (arr[j][i]) {
                arr[1][idx++] = arr[j][i];

                if (j == 1 && i == idx - 1) continue;
                arr[j][i] = 0;
            }
        }
    }
}


void reJumpBlock() {
    for (int i = 1; i <= N / 2; i++) {
        arr[2][N - i + 1] = arr[1][i];
        arr[1][i] = 0;
    }

    for (int i = 0; i < N / 4; i++) {
        for (int j = 0; j < 2; j++) {
            arr[3 + j][N - i] = arr[2 - j][N / 2 + 1 + i];
            arr[2 - j][N / 2 + 1 + i] = 0;
        }
    }
}

bool isEnd() {
    int max = -1;
    int min = INT_MAX;

    for (int i = 1; i <= N; i++) {
        if (max < arr[1][i]) max = arr[1][i];
        if (min > arr[1][i]) min = arr[1][i];
    }
    return (max - min <= K);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> arr[1][i];
    }

    if (isEnd()) {
        cout << 0 << '\n';
        return 0;
    }

    int ans = 1;
    while (1) {
        addFish();
        jumpBlock();
        fishControl();
        putDown();
        reJumpBlock();
        fishControl();
        putDown();
        if (isEnd()) break;
        ans++;
    }


    cout << ans << '\n';

    return 0;
}

https://www.acmicpc.net/problem/23290

물고기를 한마리 한마리 처리하는 게 아니라

같은 좌표에서 같은 방향을 가리키는 물고기가 몇마리 있는 지 세어주는 식으로 구현하면

메모리를 상당히 아낄 수 있다.

처음에 문제를 읽을 때는 물고기 한마리 한마리 벡터에 넣어주면서 풀었는데

어차피 중요한건 물고기의 수이므로 같은 좌표 같은 방향 물고기를 한번에 이동시켜주면

메모리와 함께 시간도 절약할 수 있다.

그리고 상어의 이동은 3칸이동하므로 간단히 반복문으로 구현하고

이동 내에서 중복된 칸이 있는지 체크하기 위해 set을 이용하여 여러번 방문한 칸이어도

물고기들을 한번만 없애주도록 만들었다.

#include <bits/stdc++.h>

using namespace std;

int skx, sky, S, smell[5][5];
int fishes[5][5][9], fishCopy[5][5][9];

void Input() {
    int M;
    cin >> M >> S;
    for (int i = 1; i <= M; i++) {
        int fx, fy, d;
        cin >> fx >> fy >> d;
        fishes[fx][fy][d]++;
    }
    cin >> skx >> sky;
}

void copyMagic() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 8; k++) {
                fishCopy[i][j][k] = fishes[i][j][k];
            }
        }
    }
}

void fishesMove() {
    int dx[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
    int dy[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};

    int tmp[5][5][9];
    memset(tmp, 0, sizeof(tmp));
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 8; k++) {
                int dir = k;
                bool flag = false;
                for (int t = 1; t <= 8; t++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];
                    if (nx <= 0 || nx > 4 || ny <= 0 || ny > 4 || smell[nx][ny] || (nx == skx && ny == sky)) {
                        //반시계회전
                        dir = dir - 1;
                        if (dir == 0) dir = 8;
                    } else {
                        flag = true;
                        tmp[nx][ny][dir] += fishes[i][j][k];
                        break;
                    }
                }
                //이동할 수 없는 경우
                if (!flag) {
                    tmp[i][j][k] += fishes[i][j][k];
                }
            }
        }
    }
    swap(tmp, fishes);
}

void sharkMove() {
    int dx[5] = {0, -1, 0, 1, 0};
    int dy[5] = {0, 0, -1, 0, 1};

    int maxSum = -1;
    int nskx = -1, nsky = -1;
    vector<pair<int, int> > toSmell;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for (int k = 1; k <= 4; k++) {
                int firstX = skx + dx[i], firstY = sky + dy[i];
                int secX = firstX + dx[j], secY = firstY + dy[j];
                int thirdX = secX + dx[k], thirdY = secY + dy[k];

                if (firstX <= 0 || firstX > 4 || firstY <= 0 || firstY > 4) continue;
                if (secX <= 0 || secX > 4 || secY <= 0 || secY > 4) continue;
                if (thirdX <= 0 || thirdX > 4 || thirdY <= 0 || thirdY > 4) continue;
                int sum = 0;
                set<pair<int, int> > Set;
                Set.insert({firstX, firstY});
                Set.insert({secX, secY});
                Set.insert({thirdX, thirdY});
                for (auto a: Set) {
                    for(int b=1; b<=8; b++){
                        sum += fishes[a.first][a.second][b];
                    }
                }
                if (sum > maxSum) {
                    maxSum = sum;
                    toSmell.clear();
                    nskx = thirdX;
                    nsky = thirdY;
                    for (auto a: Set) {
                        toSmell.push_back({a.first, a.second});
                    }
                }
            }
        }
    }
    for (auto a: toSmell) {
        int sum = 0;
        for(int b=1; b<=8; b++){
            sum += fishes[a.first][a.second][b];
        }
        if (sum) {
            smell[a.first][a.second] = 3;
            memset(fishes[a.first][a.second], 0 ,sizeof(fishes[a.first][a.second]));
        }
    }
    skx = nskx;
    sky = nsky;
}

void smellErase() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (smell[i][j]) {
                smell[i][j]--;
            }
        }
    }
}

void appendCopy() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for(int k=1; k<=8 ;k++){
                fishes[i][j][k] += fishCopy[i][j][k];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    Input();
    for (int i = 0; i < S; i++) {
        copyMagic();
        fishesMove();
        sharkMove();
        smellErase();
        appendCopy();
    }

    int ans = 0;
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            for(int k=1; k<=8 ;k++){
                ans += fishes[i][j][k];
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

https://www.acmicpc.net/problem/23289

문제를 해결하기 위해서는 상당한 기합이 필요하다..

#include <bits/stdc++.h>

using namespace std;

int chocolate, R, C, K, W, Map[21][21];
bool Wall[21][21][4];
vector<pair<int, int> > toCheck;
vector<tuple<int, int, int> > hotAirBlower;

void warmAir() {
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};

    //hd, x, y
    int nextDir[4][2][3] = {
            {{-1, 0,  1},  {1,  1,  1}},
            {{-1, 0,  1},  {-1, -1, -1}},
            {{-1, -1, -1}, {1,  0,  -1}},
            {{1,  1,  1},  {1,  0,  -1}}
    };

    for (auto h: hotAirBlower) {
        int addWarm[21][21];
        memset(addWarm, 0, sizeof(addWarm));

        auto [hx, hy, hd] = h;
        queue<pair<int, int> > Q;
        int stx = hx + dx[hd];
        int sty = hy + dy[hd];

        Q.push({stx, sty});
        addWarm[stx][sty] = 5;
        while (!Q.empty()) {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();

            if (addWarm[x][y] == 1) continue;
            for (int i = 0; i < 3; i++) {
                int nx = x + nextDir[hd][0][i];
                int ny = y + nextDir[hd][1][i];

                if (nx <= 0 || nx > R || ny <= 0 || ny > C) continue;
                if (addWarm[nx][ny]) continue;
                //사이에 벽이 있는 경우
                if (abs(nx - x) && abs(ny - y)) { //대각선
                    if (hd == 0) {
                        if (nx - x > 0) {
                            if (Wall[x][y][2] || Wall[nx][ny][3]) continue;
                        } else {
                            if (Wall[x][y][0] || Wall[nx][ny][3]) continue;
                        }
                    } else if (hd == 1) {
                        if (nx - x > 0) {
                            if (Wall[x][y][2] || Wall[nx][ny][1]) continue;
                        } else {
                            if (Wall[x][y][0] || Wall[nx][ny][1]) continue;
                        }
                    } else if (hd == 2) {
                        if (ny - y > 0) {
                            if (Wall[x][y][1] || Wall[nx][ny][2]) continue;
                        } else {
                            if (Wall[x][y][3] || Wall[nx][ny][2]) continue;
                        }
                    } else {
                        if (ny - y > 0) {
                            if (Wall[x][y][1] || Wall[nx][ny][0]) continue;
                        } else {
                            if (Wall[x][y][3] || Wall[nx][ny][0]) continue;
                        }
                    }
                } else {
                    if (nx - x == 1 && Wall[x][y][2]) continue;
                    else if (nx - x == -1 && Wall[x][y][0])continue;
                    else if (ny - y == 1 && Wall[x][y][1]) continue;
                    else if (ny - y == -1 && Wall[x][y][3]) continue;
                }
                addWarm[nx][ny] = addWarm[x][y] - 1;

                Q.push({nx, ny});
            }
        }

        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                Map[i][j] += addWarm[i][j];
            }
        }

    }
}

void temperatureControl() {
    int tmp[21][21];
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};


    for (int x = 1; x <= R; x++) {
        for (int y = 1; y <= C; y++) {
            int curTemper = Map[x][y];
            int sum = 0;
            int minus = 0;

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if (nx <= 0 || nx > R || ny <= 0 || ny > C) continue;
                //벽
                if (nx - x == 1 && Wall[x][y][2]) continue;
                else if (nx - x == -1 && Wall[x][y][0])continue;
                else if (ny - y == 1 && Wall[x][y][1]) continue;
                else if (ny - y == -1 && Wall[x][y][3]) continue;

                if (Map[nx][ny] > Map[x][y]) {
                    sum += abs(Map[nx][ny] - Map[x][y]) / 4;
                } else if (Map[nx][ny] < Map[x][y]) {
                    minus += abs(Map[nx][ny] - Map[x][y]) / 4;
                }
            }
            tmp[x][y] = curTemper + sum - minus;
        }
    }
    swap(tmp, Map);
}

void temperatureMinus() {
    for (int i = 1; i <= R; i++) {
        if (Map[i][1]) Map[i][1]--;
        if (Map[i][C]) Map[i][C]--;
    }
    for (int i = 2; i <= C-1; i++) {
        if (Map[1][i]) Map[1][i]--;
        if (Map[R][i]) Map[R][i]--;
    }
}

bool endCheck() {
    if(chocolate > 100) return true;
    for (auto a: toCheck) {
        if (Map[a.first][a.second] < K) return false;
    }
    return true;
}

void Input() {
    cin >> R >> C >> K;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            int num;
            cin >> num;
            if (num == 5) {
                toCheck.push_back({i, j});
            } else if (num > 0) {
                hotAirBlower.push_back({i, j, num - 1});
            }
        }
    }
    cin >> W;
    for (int i = 1; i <= W; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        if (t == 0) {
            Wall[x][y][0] = 1;
            Wall[x - 1][y][2] = 1;
        } else {
            Wall[x][y][1] = 1;
            Wall[x][y + 1][3] = 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    Input();

    do {
        warmAir();
        temperatureControl();
        chocolate++;
        temperatureMinus();
    } while (!endCheck());

    cout << ((chocolate > 100) ? 101 : chocolate) << '\n';

    return 0;
}

https://www.acmicpc.net/problem/23288

#include <bits/stdc++.h>

using namespace std;

int N, M, K, Map[21][21], pointMap[21][21], ans;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int moveDirection = 0;
//dice는 문제의 나온 전개도랑 다릅니다. 제가 문제에 제시된걸 안보고 풀어서 그렇습니다..
int dice[6] = {6, 5, 1, 2, 4, 3};
int floorX = 1, floorY = 1;

void drawPointMap() {
    queue<pair<int, int> > Q;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (pointMap[i][j] == 0) {
                vector<pair<int, int> > v;
                Q.push({i, j});
                //방문체크
                pointMap[i][j] = -1;
                v.push_back({i, j});

                while (!Q.empty()) {
                    int x = Q.front().first;
                    int y = Q.front().second;
                    Q.pop();

                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        if (nx <= 0 || nx > N || ny <= 0 || ny > M) continue;
                        if (Map[nx][ny] == Map[i][j] && pointMap[nx][ny] != -1) {
                            Q.push({nx, ny});
                            v.push_back({nx, ny});
                            pointMap[nx][ny] = -1;
                        }
                    }
                }
                for (int k = 0; k < v.size(); k++) {
                    pointMap[v[k].first][v[k].second] = Map[i][j] * v.size();
                }
            }
        }
    }
}

void turnMoveDirection() {
    if (dice[0] > Map[floorX][floorY]) {
        moveDirection = (moveDirection + 1) % 4;
    } else if (dice[0] < Map[floorX][floorY]) {
        moveDirection = (moveDirection + 3) % 4;
    }
}

void diceToRight() {
    int tmp = dice[0];
    dice[0] = dice[5];
    dice[5] = dice[2];
    dice[2] = dice[4];
    dice[4] = tmp;
}

void diceToDown() {
    int tmp = dice[3];
    dice[3] = dice[0];
    dice[0] = dice[1];
    dice[1] = dice[2];
    dice[2] = tmp;
}


void checkAndMove() {
    // 아랫면 좌표 이동
    int x = floorX + dx[moveDirection];
    int y = floorY + dy[moveDirection];
    if (x <= 0 || x > N || y <= 0 || y > M) {
        moveDirection = (moveDirection + 2) % 4;
        x = floorX + dx[moveDirection];
        y = floorY + dy[moveDirection];
    }
    floorX = x;
    floorY = y;


    //주사위 이동
    if (moveDirection == 0) {
        diceToRight();
    } else if (moveDirection == 2) {
        for (int i = 0; i < 3; i++) diceToRight();
    } else if (moveDirection == 1) {
        diceToDown();
    } else {
        for (int i = 0; i < 3; i++) diceToDown();
    }
    
    ans += pointMap[floorX][floorY];
    turnMoveDirection();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> Map[i][j];
        }
    }


    drawPointMap();

    for (int i = 1; i <= K; i++) checkAndMove();


    cout << ans << '\n';

    return 0;
}

https://www.acmicpc.net/problem/21611

1.문제설명

해당 문제에서 거쳐야하는 과정을 크게 4가지로 분리할 수 있다.

1. 블리자드해서 구슬을 삭제한다.

2. 구슬의 빈자리를 메꾸도록 모든 구슬을 앞으로 이동시킨다.

3. 구슬폭발 : 이동후 같은 구슬이 4개 이상 모여있는 구슬들을 삭제한다. (삭제후 2번과 동일하게 앞으로 이동)

4. 구슬변화 : 남아있는 구슬을 확인하면서, 연속된 구슬의 개수와 해당 구슬의 숫자로 구슬을 변화시킨다.

이 문제를 풀기 위한 배열과 연결리스트 중 어떤 자료구조를 선택할 지 고민했는데,

구슬폭발로 인해 원소를 자주 삭제해야하니까 연결리스트가 시간복잡도 상 유리하지 않을까 생각했다.

그런데 좀 더 생각해보니 구슬이 폭발한다고 원소를 바로 바로 삭제해서 푸는게 아니라

폭발하기 전 배열에서 폭발할 구슬들을 확인한 후 제외하는 방식으로 풀어야하기 때문에

인덱스 접근을 해야할 일이 많아서 배열로 푸는 것으로 결정했다.

의문이 들었던 것 중 하나는

4. 구슬변화 후 다시 구슬폭발이 일어나는 경우가 있지 않을 까 의심했는데,

깊이 생각해보니 구슬폭발이 모두 끝난 후에는 구슬 변화로 인해 연속적인 구슬 4개가 생길 수 없다.

예를 들어서 2가 2개 있는 경우, 또 2가 2개있는 경우 이러면 2222가 되니까 또 폭발할 수 있지 않을 까 생각했는데

애초에 구슬폭발이 모두 끝난 경우에는 2가 2개, 2가 2개 이런 경우가 나타날 수 없다.

다른 경우도 마찬가지이다.

문제에서 2차원 배열 형식으로 그림을 제공했지만

이를 1차원 배열로 전환한 후 문제를 해결해야한다.

반복문을 통해서 2차원배열의 1번부터 N*N-1번까지 돌 수 있다.

블리자드를 구현할 때는 1차원 배열내에서 가능한데,

계차수열을 이용해서 1차원 배열에서 반복문을 돌면서 배열의 원소를 지워나가면 해결할 수 있다.

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int N, M, originArr[51][51], marbles[2501], ans[4];

void originToMarbles() {
    int x = (N + 1) / 2;
    int y = x;

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

    int curDir = 0;
    int moveCnt = 1;
    int turnDirCnt = 0;

    for (int i = 0; i < N * N; i++) {
        marbles[i] = originArr[x][y];
        turnDirCnt++;

        x += dx[curDir];
        y += dy[curDir];

        if (turnDirCnt == moveCnt) {
            if (curDir == 1 || curDir == 3) moveCnt++;
            curDir = (curDir + 1) % 4;
            turnDirCnt = 0;
        }
    }
}

void blizzard(int d, int s) {
    int firstNum[5] = {0, 7, 3, 1, 5};
    int firstStep[5] = {0, 15, 11, 9, 13};

    int num = firstNum[d];
    int step = firstStep[d];
    for (int i = 1; i <= s; i++) {
        marbles[num] = 0;
        num += step;
        step += 8;
    }
}

void marbleMove() {
    int tmp[2501];
    memset(tmp, 0, sizeof(tmp));
    int tmpIdx = 1;

    for (int i = 1; i < N * N; i++) {
        if (marbles[i] == 0) continue;
        tmp[tmpIdx++] = marbles[i];
    }
    swap(marbles, tmp);
}

bool marbleExplode() {
    bool flag = false;
    int sameFirst = 1;
    int sameCnt = 1;
    for (int i = 2; i <= N * N; i++) {
        if (marbles[i] != 0 && marbles[i] == marbles[i - 1]) {
            sameCnt++;
        } else {
            if (sameCnt >= 4) {
                ans[marbles[i-1]] += i - sameFirst;
                for (int j = sameFirst; j <= i - 1; j++) {
                    marbles[j] = 0;
                }
                flag = true;
            }
            sameFirst = i;
            sameCnt = 1;
        }
    }
    return flag;
}

void marbleChange() {
    int tmp[2501];
    memset(tmp, 0 ,sizeof(tmp));
    int tmpIdx = 1;

    int sameCnt = 1;
    for(int i=2; i<=N*N; i++){
        if(marbles[i]==marbles[i-1]){
            sameCnt++;
        }
        else{
            tmp[tmpIdx++] = sameCnt;
            if(tmpIdx == N*N) break;
            tmp[tmpIdx++] = marbles[i-1];
            if(tmpIdx == N*N) break;
            sameCnt = 1;
        }
    }
    swap(tmp, marbles);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> originArr[i][j];
        }
    }

    originToMarbles();


    for (int i = 1; i <= M; i++) {
        int d, s;
        cin >> d >> s;
        blizzard(d, s);
        marbleMove();
        while (marbleExplode()) {
            marbleMove();
        }
        marbleChange();
    }
    
    cout << ans[1] + 2 * ans[2] + 3 * ans[3] << '\n';
    return 0;
}