[16236号サメ]-C++

[16236号サメ]
https://www.acmicpc.net/problem/16236
[19236号青少年サメ]
https://www.acmicpc.net/problem/19236
https://velog.io/@statco19/boj-19236
[19237号サメ]
https://www.acmicpc.net/problem/19237
https://velog.io/@statco19/boj-19237
これは子供-青少年-大人サメシリーズの最初の問題です.
これは最短距離を探すBFSを利用した比較的簡単な実装問題である.中間に現れる分割誤りや参照字文法に慣れていないところは,実現にかなりの時間を費やした.

に答える

この問題で忘れがちな部分は、入力時に魚の開始位置もスペースと見なすべきだということです.したがって、9を入力すると現在の位置に保存されますが、セルは0に変更する必要があります.

1.

サメの現在位置でBFSを使って自分より小さい魚を探します.BFSで見つけたので、距離は最小の保証があります.

2.

複数の魚の距離が最小であれば,魚の位置を保存したvectorをループし,条件に合った魚の座標を求める.座標に対応する領域を0に設定し、食用とする.

3.

食べる魚の数が現在の魚の大きさと同時に1匹の魚の大きさを増やし、食べる魚の数を0に再初期化します.

4.

食べられる魚がいないために初期最短距離値-1を返すと、すべてを停止し、これまで移動していた距離に出力します.

C++コード

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans;
int n;
int sharkSize = 2;
int eatenFish = 0;  // # of fish eaten
int map[21][21];
int visited[21][21];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int r,c;

int fishDist(int& r, int& c) {
	int dist = 0;
	int found = 0;

	queue<pair<int,int> > q;
	vector<pair<int,int> > arr;

	q.push(make_pair(r,c));

	while(!q.empty() && !found) {
		dist++;
		int size = q.size();

		for(int k=0;k<size;++k) {
			pair<int,int> p = q.front();
			q.pop();

			int i,j;
			i = p.first;
			j = p.second;
			visited[i][j] = 1;

			for(int d=0;d<4;++d) {
				int ni,nj;
				ni = i+dr[d];
				nj = j+dc[d];

				if(!(1 <= ni && ni <= n && 1 <= nj && nj <= n)) {
					continue;
				}

				if(!visited[ni][nj]) {
					visited[ni][nj] = 1;
					if(map[ni][nj] == 0) {
						q.push(make_pair(ni,nj));
					}
					else if(map[ni][nj] <= sharkSize) {
						if(map[ni][nj] < sharkSize) {  // fish to eat found
							arr.push_back(make_pair(ni,nj));
							if(!found) {
								found = 1;
							}
						} else {
							q.push(make_pair(ni,nj));
						}
					}
				}
			}
		}
	}

	if(arr.size() == 0) {
		return -1;
	}

	int row,col;
	row=987654321;
	col=987654321;

	for(int i=0;i<arr.size();++i) {
		pair<int,int>& p = arr[i];
		int R,C;
		R = p.first;
		C = p.second;
		if(R < row) {
			row = R;
			col = C;
		} else if(R == row) {
			col = min(C,col);
		}
	}

	map[row][col] = 0;  // eat fish
	r = row;
	c = col;
	if(++eatenFish == sharkSize) {
		sharkSize++;
		eatenFish = 0;
	}

	return dist;
}

void sol() {
	
	while(true) {
		memset(visited,0,sizeof(visited));
		int dist;
		dist = fishDist(r,c);
		
		if(dist == -1) {  // no fish to eat
			break;
		}
		ans += dist;
	}

	return;
}

int main(void) {
	// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	scanf("%d", &n);

	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			scanf("%d", &map[i][j]);
			if(map[i][j] == 9) {  // shark position
				r = i;
				c = j;
				map[i][j] = 0;
			}
		}
	}

	sol();

	printf("%d\n", ans);
	
	return 0;
}

実行結果