[ 백준 23290 ] 마법사 상어와 복제 (C++)

백준의 마법사 상어와 복제(23290) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 문제에 맞게 진행했을 때 최종적으로 물고기가 격자에 몇 마리가 남아있는지 구해야 하는 문제이다.

(이 글을 읽기 전에, 문제를 해결하지 못하신 것은 상관이 없지만, 문제에서 무엇을 구현해야 하는지와 같은 문제에 대한 이해는 완벽하게 하고 오시는 것을 권장드립니다.)

 

이 문제는 여러 개의 단계로 나눠져 있는데 각 단계별로 구현 과정에 대해서 이야기해보고 이를 통해 정답을 도출하는 과정까지 진행해보자.

 

#1. 맵 관리

가장 먼저, 맵을 어떻게 관리할지에 대해서부터 이야기를 해보자.

맵에 대해서 이야기 하기 전에, "물고기"에 대해서부터 이야기를 해보자.

물고기는 크게 2가지 정보를 가지고 있다. 바로, 물고기의 위치와 물고기의 진행방향이다.

물고기의 위치를 조금 더 구체적으로 써보면 (x , y)를 가지고 있을 것이고, 그리고 물고기의 진행방향 총 3가지에 대한 정보를 가지고 있다. 그래서 본인은, fish라는 위에서 이야기한 3개의 데이터를 멤버변수로 갖는 구조체를 만들어서 관리해 주었다.

struct fish {
	int x;
	int y;
	int dir;
};

그리고, 위의 구조체를 자료형으로 가지는 2차원 Vector 배열을 맵으로 만들어 주었다.

왜 Vector를 이용했을까 ?? 왜냐하면, 한 칸에 여러 마리의 물고기가 동시에 존재할 수 있기 때문이다.

그렇기 때문에 2차원 Vector배열을 선언해 주었다.

vector<fish> fishMap[MAX][MAX] 이와 같이 선언해 주었다.

그리고, 각각의 좌표에는 해당 좌표에 존재하는 물고기들의 정보를 저장해 주었다.

이를 바탕으로 입력받는 부분을 코드로 한번 살펴보자.

struct fish {
	int x;
	int y;
	int dir;
};

int n = 4, m, s;
vector<fish> fishMap[MAX][MAX];
pair<int, int> shark;

void input() {
	cin >> m >> s;
	for (int i = 0; i < m; i++) {
		int x, y, d;
		cin >> x >> y >> d;
		x--; y--;
		fish f = { x, y, d };
		fishMap[x][y].push_back(f);
	}
	cin >> shark.first >> shark.second;
	shark.first--; shark.second--;
}

 

#2. Process1 - 물고기 복제하기

이제 본격적으로, 문제를 풀어보자.

가장 첫 번째 단계는 모든 물고기들에게서 복제 마법을 시전하는 것이다. 즉, 현재 물고기들이 있는 좌표에 그대로 물고기들이 복제되는 것이다. 현재 맵을 그대로 복사만 하면 되는 것이기 때문에 본인은, 또 하나의 맵을 만들어서 임시적으로 저장만 해주었다.

vector<fish> fishMap[MAX][MAX], cMap[MAX][MAX];

void copyMap(vector<fish> A[][MAX], vector<fish> B[][MAX]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			A[i][j] = B[i][j];
		}
	}
}

void copyFish() {
	copyMap(cMap, fishMap);
}

물고기를 복제하는 과정을 위해 호출하는 함수는 copyFish() 함수이고, copyFish() 함수에서는 MAP을 복사하는 copyMap() 함수를 호출하게 된다. 즉, 위에 선언되어 있는 'cMap[MAX][MAX]' 라는 2차원 Vector배열에는 현재 1단계에 존재하는 물고기들의 상태를 그대로 저장되어지게 된다.

 

#3. Process2 - 물고기 이동하기

물고기가 진행방향으로 나아갈 수 있다면, 나아가고 그게 아니라면 진행방향을 반시계 방향으로 45도 회전하면서 시도하게 되는 과정을 구현해야 한다. 일단 우리가 입력받은 대로라면, 우리는 맵의 모든 좌표를 탐색하면서 해당 좌표에 존재하는 물고기들의 정보들을 가지고 물고기를 움직여 주면 된다. 그리고, 물고기가 나아갈 수 있는 좌표를 찾아서 움직이게 된다면, 해당 좌표에 해당 물고기의 정보를 넣어주면 된다. 하지만, 본인은 임시 적으로 물고기의 정보를 저장하는 tempMap을 만들어서 물고기의 정보를 저장해 주었다. 왜 그래야만 할까 ?? 주어진 맵을 가장 왼쪽 위의 좌표가 (1 , 1) 가장 오른쪽 아래의 좌표가 (4 , 4)라고 가정해보자. 그리고 우리는 (1 , 1)부터 순차적으로 (4 , 4)까지 탐색을 하게 될 것이다.

그런데, (1 , 1)에 있는 물고기 한마리가 오른쪽으로 진행방향을 가져서, (1 , 2)로 갔다고 가정해보자.

그럼 우리는 당연히 map[1][2]에 이 물고기에 대한 정보를 넣어주게 될 것이다.

그리고, (1 , 1)을 탐색을 다 했으니, 그 다음인 (1 , 2)를 탐색을 한다고 가정해보자. (1 , 2)에는 (1 , 1)에서 움직여서 오게 된 물고기가 존재한다. 그런데, 이를 따로 처리해주지 않고 그대로 물고기를 움직여 준다면, (1 , 1)에서 (1 , 2)로 움직여서 오게 된 물고기도 또 움직이게 될 것이다. 즉 ! 기존의 map에다가 계속해서 물고기의 정보를 옮겨가면서 계산을 하다보면 위와 같이 잘못된 계산이 이뤄지는 경우가 발생할 수도 있다.

그래서, 물고기가 움직이게 되면, 해당 물고기를 map[1][2]에 넣어주는 것이 아닌, tempMap[1][2] 에 넣어주었다.

그리고, (1 , 2)에 대한 계산을 할 때에는 map[1][2]에 대해서만 계산을 하는 것이다. 그렇게 되면, 기존에 (1 , 2)에 있는 물고기들에 대해서만 계산이 이루어지게 될 것이다.

최종적으로, tempMap에 있는 물고기의 상태를 원본 Map으로 다시 옮겨주기만 하면 된다.

이 외에, 물고기의 방향을 바꾼다거나 물고기가 갈 수 없는 칸인지를 확인해야 하는 과정들도 있는데, 이 과정에서 소개하지 않은 하나의 변수가 새롭게 등장하게 된다.

바로, smellMap 이라는 int형 2차원 배열이다. smellMap[A][B] = C 의 의미는, (A , B)에서 가장 최근에 냄새가 있던 시점은 C입니다 를 의미한다. 이 smellMAP에 대해서는 아래쪽에서 조금 더 구체적으로 이야기를 해보도록 하자.

무튼 ! 여기서는 간략하게만 말해보자면, smellMap[x][y] = 0 인 경우에만 이동이 가능하다. smellMap[x][y] = 0 이라는 것은, 해당 좌표에 물고기의 냄새가 존재하지 않는다는 것을 의미하기 때문이다.

int smellMap[MAX][MAX];
int fdx[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };	// fdx[] = fishdx를 의미.
int fdy[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 }; 	// fdy[] = fishdy를 의미.

int changeDir(int dir) {
	switch (dir) {
	case 1:
		return 8;
	case 2:
		return 1;
	case 3:
		return 2;
	case 4:
		return 3;
	case 5:
		return 4;
	case 6:
		return 5;
	case 7:
		return 6;
	case 8:
		return 7;
	}
}

void moveFish() {
	vector<fish> tempMap[MAX][MAX];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < fishMap[i][j].size(); k++) {
				int x = fishMap[i][j][k].x;
				int y = fishMap[i][j][k].y;
				int dir = fishMap[i][j][k].dir;
				int nx = x;
				int ny = y;
				bool Flag = false;
				for (int l = 0; l < 8; l++) {
					nx = x + fdx[dir];
					ny = y + fdy[dir];
					if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
						if ((nx != shark.first || ny != shark.second) && smellMap[nx][ny] == 0) {
							Flag = true;
							break;
						}
					}
					dir = changeDir(dir);
				}
				if (Flag == true) {
					fish f = { nx, ny, dir };
					tempMap[nx][ny].push_back(f);
				}
				else {
					fish f = { x, y, dir };
					tempMap[x][y].push_back(f);
				}
			}
		}
	}
	copyMap(fishMap, tempMap);
}

 

#4. Process3 - 상어 움직이기

연속해서 3칸을 상어는 움직이게 된다. 상하좌우로 인접한 칸만 움직일 수 있다. 그리고, 상어는 가장 많은 물고기를 먹을 수 있는 루트로 움직이게 된다. 물고기의 수가 같을 때는, 상어의 움직임이 가지는 우선순위를 따졌을 때, 가장 우선순위가 높은 움직임으로 움직이게 된다. 지금부터 구체적으로 이야기를 해보자.

본인은 이를 "중복순열"을 통해서 접근하였다. 다시 말해서, 상어가 움직여야 하는 3칸의 방향을 중복순열을 통해서 찾아 주었다. 왜 중복순열일까?? 먼저 , 중복이 선택되는 이유에 대해서 알아보자. 상어가 3칸을 움직여야 하는데, 3칸 모두 상상상 의 방향으로 움직이는 것이 가능하다. 즉 ! 어느 한 방향이 기존에 한번 나왓다고 해서 그 방향으로 더 이상 못움직이는 것이 아니다. 그러므로 중복적으로 선택이 가능하다. 두 번째로, 왜 순열일까 ?? 상어가 상하상 으로 움직이는 경우와 상상하로 움직이는 경우를 생각해보자. 똑같이 위쪽으로 2번 움직이고 아래쪽으로 1번 움직이는 것이지만 그 순서만 다를 뿐이다. 하지만 위의 2개의 움직임에 대한 결과는 너무나도 크게 다를 것이다. 그렇기 때문에, 선택한 데이터의 순서에 영향을 미치기 때문에 조합이 아닌 순열을 통해서 구현해 주었다. 아직 중복순열에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 중복순열에 대해서 알아보기(Click) ]

 

중복순열을 통해서, 발생할 수 있는 모든 경우의 수를 발생시키고, 발생된 경우마다 움직여보면서 물고기를 얼마나 잡아먹을 수 있는지를 Count 해주면 된다. 대신 ! 발생된 경우마다 움직여줄 때, 실제로 물고기에 대한 정보를 없애버리거나 그러면 안된다. 왜냐하면, 예를 들어서 처음에 상상상 의 방향으로 움직였다고 가정해보자. 그런데 이 때, 상상상에 있는 물고기들을 모두 없애고 그 이후에 상상우의 방향으로 움직였다고 가정해보자. 그렇게 되면, '상상'에 있는 물고기는 '상상상'의 방향으로 움직일 때 이미 없어진 물고기이기 때문에 '상상우'로 움직일 때 Count되지 않을 것이고, 결국 독립적으로 시행되어야 하는 경우가 서로에게 영향을 미쳐버리게 되기 때문이다. 그렇기 때문에 실제로 물고기를 없앨거면 다시 물고기를 복원시켜놓아야 한다. 본인은 실제로 없애지는 않고, 방문처리를 통해서 단순히 먹을 수 있는 물고기의 수를 계산해 주었다. 이 부분에 대한 소스코드는 아래와 같다.

int sdx[] = { 0, -1, 0, 1, 0 };
int sdy[] = { 0, 0, -1, 0, 1 };
int tempRoute[3], route[3];	
// tempRoute[3] = 중복순열을 통해 발생한 경우, Simulation을 위해 상어의 이동방향을 저장하는 배열
// route[3] = Simulation을 통해, 가장 많은 물고기를 먹을 수 있는 상어의 이동방향을 저장하는 배열
int maxEating;

int routeSimulation() {
	bool visit[MAX][MAX] = { false, };
	int x = shark.first;
	int y = shark.second;
	int eat = 0;
	for (int i = 0; i < 3; i++) {
		int dir = tempRoute[i];
		int nx = x + sdx[dir];
		int ny = y + sdy[dir];
		if (nx < 0 || ny < 0 || nx >= n || ny >= n) return -1;
		if (visit[nx][ny] == false) {
			visit[nx][ny] = true;
			eat += fishMap[nx][ny].size();
		}
		x = nx;
		y = ny;
	}
	return eat;
}

void findRoute(int cnt) {
	if (cnt == 3) {
		int eatNum = routeSimulation();
		if (eatNum > maxEating) {
			for (int i = 0; i < 3; i++) {
				route[i] = tempRoute[i];
			}
			maxEating = eatNum;
		}
		return;
	}

	for (int i = 1; i <= 4; i++) {
		tempRoute[cnt] = i;
		findRoute(cnt + 1);
	}
}

void moveShark(int time) {
	vector<fish> tempMap[MAX][MAX];
	copyMap(tempMap, fishMap);

	int x = shark.first;
	int y = shark.second;
	for (int i = 0; i < 3; i++) {
		int dir = route[i];
		int nx = x + sdx[dir];
		int ny = y + sdy[dir];
		if (tempMap[nx][ny].size() != 0) {
			smellMap[nx][ny] = time;
			tempMap[nx][ny].clear();
		}
		x = nx;
		y = ny;
		shark.first = x;
		shark.second = y;
	}
	copyMap(fishMap, tempMap);
}

void aboutShark(int time) {
	maxEating = -1;
	findRoute(0);
	moveShark(time);
}

그런데 위의 코드를 보면, 문제에서 제시한 "상어의 이동방향에 대한 우선순위 계산"이 전혀 들어있지 않다.

왜그럴까 ?! 왜냐하면 애초에 상어의 움직임의 순서를 우선순위 순서대로 넣어주었기 때문이다.

가장 위에 sdx[]와 sdy[]를 보면, 이게 상어가 인접한 칸으로 움직일 때 x변화값과 y변화값이다.

그런데, 저 순서를 잘 보면, 상좌하우 순서대로 존재한다.

즉, sdx,y[1] = 상 으로 움직이는 경우. sdx,y[2] = 좌로 움직이는 경우. sdx,y[3] = 하로 움직이는 경우, sdx,y[4] = 우로 움직이는 경우이다. 그리고 중복순열을 뽑을 때는 1번부터 순차적으로 뽑게된다.

즉 ! 중복순열로 3개의 이동방향을 뽑았을 때, 가장 먼저 나오는 것은 '111' 즉, 상상상을 의미하게 된다.

가장 마지막으로 나오는 것은 '444' 즉, 우우우가 될 것이다. 즉 ! 물고기를 먹은 수가 동일한 경우에는 우선순위를 따져줘야 하는데, 굳이 따져줘도 되지 않아도 되는 이유는 기존에 최대로 먹었던 물고기의 수와 현재 케이스로 먹은 물고기 수가 동일하다면 기존 진행방향이 더 우선순위가 자연스럽게 더 높아지게 된다. 그래서 findRoute() 함수에서 line31)에서 보게 되면, 물고기의 수가 동일한 경우에는 계산조차 하지 않는다. 왜냐하면 동일한 경우에는 값의 갱신이 일어나지 않는 것이 맞기 때문이다.

 

#5. Process4 - 물고기 냄새

#4의 내용과 매우 이어지는 내용이다. #4에서 소스코드에도 잠깐 보였겠지만, 아무런 언급을 일부러 하지도 않았다.

한 가지 상황을 생각해보자. (x , y)라는 좌표에서 1초에 물고기가 죽어서 냄새를 남겼다고 가정해보자.

4초에는 (x , y)에 냄새가 남아있을까 ?? 남아있지 않다.

그럼, (x , y)라는 좌표에서 물고기가 1초에 죽어서 냄새를 남겼고, 그 이후에 (x , y)에서 물고기가 3초에 죽어서 냄새를 남겼다고 생각해보자. 4초에는 (x , y)에는 냄새가 남아있을까 ?? 냄새가 남아있다.

그럼, (x , y)에서 2초에 한마리가 죽고, 3초에 한마리가 죽었다. 4초에 (x , y)에 냄새가 남아있을까 ? 냄새가 남아있을 것이다.

너무나도 당연하고 간단한 이야기이다. 본인이 이 이야기를 통해서 하고자 하는 이야기는 다음과 같다.

"해당 좌표에서 몇 마리의 물고기가 죽었는지는 상관이 없다. 우리가 알아야 하는 것은, 현재 해당 좌표에 물고기의 냄새가 남아있는지 아닌지일 뿐이다". 이 이야기를 하고 싶다.

아까 위에서 잠깐 언급했듯이, 본인은 냄새가 있는 좌표를 관리하기 위해서 int smellMap[MAX][MAX] 라는 int형 2차원 배열을 선언해 주었다고 했다. 여기서 smellMap[MAX][MAX]의 자료형이 'int'인 이유가 위에서 했던 이야기이다.

결국, 특정 좌표에서 마지막에 죽은 물고기의 시간만 알고 있다면, smellMap에는 그 값만 넣어주면 된다.

void moveShark(int time) {
	vector<fish> tempMap[MAX][MAX];
	copyMap(tempMap, fishMap);

	int x = shark.first;
	int y = shark.second;
	for (int i = 0; i < 3; i++) {
		int dir = route[i];
		int nx = x + sdx[dir];
		int ny = y + sdy[dir];
		if (tempMap[nx][ny].size() != 0) {
			smellMap[nx][ny] = time;
			tempMap[nx][ny].clear();
		}
		x = nx;
		y = ny;
		shark.first = x;
		shark.second = y;
	}
	copyMap(fishMap, tempMap);
}

#4에서 나왔던, 상어를 움직이는 과정이다. 이 과정에서 물고기가 죽게 되는데, 물고기가 죽게 되면 해당 좌표에 smellMap 값을 설정해주는 부분이 line12)에 구현되어 있다.

여기서 smellMap의 값을 단순히 바로 현재 시간인 'time'으로 설정해주는 이유는, 지금 죽는 물고기가 해당 좌표에서 가장 마지막에 죽은 물고기가 되는 것이 자명한 사실이기 때문이다. 과연, 저렇게 상어가 움직이고 난 이후에 또 다른 요소에 의해서 저 값이 바뀔 수 있을까 ? 아니면 smellMap에 있었던 기존의 값 때문에 값이 갱신되면 안되는 그런 요소가 있을까 ?? 전혀 없다. 나는 지금 smellMap에는 "해당 좌표에서 가장 마지막에 죽은 물고기의 시간" 만 적어놓을 것이고, 그 시간은 상어에게 먹혀버리게 되는 이 순간이기 때문이다.

그럼 냄새를 없애는 과정은 어떻게 될까 ?? 다음과 같이 구현할 수 있다.

void removeSmell(int time) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (smellMap[i][j] == 0) continue;
			if (time - smellMap[i][j] == 2) {
				smellMap[i][j] = 0;
			}
		}
	}
}

 

#6. 복제된 물고기 태어나기

복제된 물고기는 cMap이라는 또 다른 맵에 저장이 되어 있을 것이고, 이 맵을 원본 map에 복사만 해주면 된다.

void bornFish() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < cMap[i][j].size(); k++) {
				fishMap[i][j].push_back(cMap[i][j][k]);
			}
		}
	}
}

 

[ 소스코드 ]

#include <iostream>
#include <vector>
 
#define endl "\n"
#define MAX 5
using namespace std;
 
struct fish {
    int x;
    int y;
    int dir;
};
 
int n = 4, m, s, maxEating;
int tempRoute[3], route[3];
int smellMap[MAX][MAX];
vector<fish> fishMap[MAX][MAX], cMap[MAX][MAX];
pair<int, int> shark;
 
int fdx[] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };
int fdy[] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
 
int sdx[] = { 0, -1, 0, 1, 0 };
int sdy[] = { 0, 0, -1, 0, 1 };
 
 
void input() {
    cin >> m >> s;
    for (int i = 0; i < m; i++) {
        int x, y, d;
        cin >> x >> y >> d;
        x--; y--;
        fish f = { x, y, d };
        fishMap[x][y].push_back(f);
    }
    cin >> shark.first >> shark.second;
    shark.first--; shark.second--;
}
 
void copyMap(vector<fish> A[][MAX], vector<fish> B[][MAX]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            A[i][j] = B[i][j];
        }
    }
}
 
void copyFish() {
    copyMap(cMap, fishMap);
}
 
int changeDir(int dir) {
    switch (dir) {
    case 1:
        return 8;
    case 2:
        return 1;
    case 3:
        return 2;
    case 4:
        return 3;
    case 5:
        return 4;
    case 6:
        return 5;
    case 7:
        return 6;
    case 8:
        return 7;
    }
}
 
void moveFish() {
    vector<fish> tempMap[MAX][MAX];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < fishMap[i][j].size(); k++) {
                int x = fishMap[i][j][k].x;
                int y = fishMap[i][j][k].y;
                int dir = fishMap[i][j][k].dir;
                int nx = x;
                int ny = y;
                bool Flag = false;
                for (int l = 0; l < 8; l++) {
                    nx = x + fdx[dir];
                    ny = y + fdy[dir];
                    if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                        if ((nx != shark.first || ny != shark.second) && smellMap[nx][ny] == 0) {
                            Flag = true;
                            break;
                        }
                    }
                    dir = changeDir(dir);
                }
                if (Flag == true) {
                    fish f = { nx, ny, dir };
                    tempMap[nx][ny].push_back(f);
                }
                else {
                    fish f = { x, y, dir };
                    tempMap[x][y].push_back(f);
                }
            }
        }
    }
    copyMap(fishMap, tempMap);
}
 
int routeSimulation() {
    bool visit[MAX][MAX] = { false, };
    int x = shark.first;
    int y = shark.second;
    int eat = 0;
    for (int i = 0; i < 3; i++) {
        int dir = tempRoute[i];
        int nx = x + sdx[dir];
        int ny = y + sdy[dir];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) return -1;
        if (visit[nx][ny] == false) {
            visit[nx][ny] = true;
            eat += fishMap[nx][ny].size();
        }
        x = nx;
        y = ny;
    }
    return eat;
}
 
void findRoute(int cnt) {
    if (cnt == 3) {
        int eatNum = routeSimulation();
        if (eatNum > maxEating) {
            for (int i = 0; i < 3; i++) {
                route[i] = tempRoute[i];
            }
            maxEating = eatNum;
        }
        return;
    }
 
    for (int i = 1; i <= 4; i++) {
        tempRoute[cnt] = i;
        findRoute(cnt + 1);
    }
}
 
void moveShark(int time) {
    vector<fish> tempMap[MAX][MAX];
    copyMap(tempMap, fishMap);
 
    int x = shark.first;
    int y = shark.second;
    for (int i = 0; i < 3; i++) {
        int dir = route[i];
        int nx = x + sdx[dir];
        int ny = y + sdy[dir];
        if (tempMap[nx][ny].size() != 0) {
            smellMap[nx][ny] = time;
            tempMap[nx][ny].clear();
        }
        x = nx;
        y = ny;
        shark.first = x;
        shark.second = y;
    }
    copyMap(fishMap, tempMap);
}
 
void aboutShark(int time) {
    maxEating = -1;
    findRoute(0);
    moveShark(time);
}
 
void removeSmell(int time) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (smellMap[i][j] == 0) continue;
            if (time - smellMap[i][j] == 2) {
                smellMap[i][j] = 0;
            }
        }
    }
}
 
void bornFish() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < cMap[i][j].size(); k++) {
                fishMap[i][j].push_back(cMap[i][j][k]);
            }
        }
    }
}
 
int findAnswer() {
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ret += fishMap[i][j].size();
        }
    }
    return ret;
}
 
void solution() {
    for (int i = 1; i <= s; i++) {
        copyFish();
        moveFish();
        aboutShark(i);
        removeSmell(i);
        bornFish();
    }
    cout << findAnswer() << endl;
}
 
void solve() {
    input();
    solution();
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    solve();
 
    return 0;
}