#include
using namespace std;
typedef pair p;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int N, ANS = 0;
int map[20][20], dist[20][20];
p shark;
int shark_size = 2;
int shark_eat = 0;
bool cmp(p& a, p& b) {
if (dist[a.first][a.second] < dist[b.first][b.second])
return true;
else if (dist[a.first][a.second] == dist[b.first][b.second])
if (a.first < b.first)
else if (a.first == b.first)
if (a.second < b.second)
return false;
}
void GetDistance(int i, int j, int d) {
if (dist[i][j] == 0 || dist[i][j] > d)
dist[i][j] = d;
else
return;
for (int t = 0; t < 4; t++) {
int ni = i + dx[t], nj = j + dy[t];
if (ni >= 0 && ni < N && nj >= 0 && nj < N)
if (map[ni][nj] <= shark_size)
GetDistance(ni, nj, d + 1);
int main(void) {
cin >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
cin >> map[i][j];
if (map[i][j] == 9)
shark.first = i, shark.second = j, map[i][j] = 0;
while (1) {
// 아기 상어가 먹을 수 있는 물고기
vector
fishes; memset(dist, 0, sizeof(int) * 20 * 20); GetDistance(shark.first, shark.second, 0); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (map[i][j] > 0 && map[i][j] < shark_size && dist[i][j]>0) fishes.push_back(make_pair(i, j)); // 먹기 if (fishes.size() == 0) { cout << ANS << endl; return 0; } else { // 가까운 애 찾아서 먹기 sort(fishes.begin(), fishes.end(), cmp); ANS += dist[fishes[0].first][fishes[0].second]; shark_eat++; if (shark_eat == shark_size) shark_size++, shark_eat = 0; map[shark.first][shark.second] = 0; ////////////이 부분 map[fishes[0].first][fishes[0].second] = 0; shark.first = fishes[0].first; shark.second = fishes[0].second; } } }
댓글을 작성하려면 로그인해야 합니다.
sotmzls 2년 전
#include
#include
#include
#include
using namespace std;
typedef pair p;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
int N, ANS = 0;
int map[20][20], dist[20][20];
p shark;
int shark_size = 2;
int shark_eat = 0;
bool cmp(p& a, p& b) {
if (dist[a.first][a.second] < dist[b.first][b.second])
return true;
else if (dist[a.first][a.second] == dist[b.first][b.second])
if (a.first < b.first)
return true;
else if (a.first == b.first)
if (a.second < b.second)
return true;
return false;
}
void GetDistance(int i, int j, int d) {
if (dist[i][j] == 0 || dist[i][j] > d)
dist[i][j] = d;
else
return;
for (int t = 0; t < 4; t++) {
int ni = i + dx[t], nj = j + dy[t];
if (ni >= 0 && ni < N && nj >= 0 && nj < N)
if (map[ni][nj] <= shark_size)
GetDistance(ni, nj, d + 1);
}
}
int main(void) {
cin >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
cin >> map[i][j];
if (map[i][j] == 9)
shark.first = i, shark.second = j, map[i][j] = 0;
}
while (1) {
// 아기 상어가 먹을 수 있는 물고기
vector
fishes; memset(dist, 0, sizeof(int) * 20 * 20); GetDistance(shark.first, shark.second, 0); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (map[i][j] > 0 && map[i][j] < shark_size && dist[i][j]>0) fishes.push_back(make_pair(i, j)); // 먹기 if (fishes.size() == 0) { cout << ANS << endl; return 0; } else { // 가까운 애 찾아서 먹기 sort(fishes.begin(), fishes.end(), cmp); ANS += dist[fishes[0].first][fishes[0].second]; shark_eat++; if (shark_eat == shark_size) shark_size++, shark_eat = 0; map[shark.first][shark.second] = 0; ////////////이 부분 map[fishes[0].first][fishes[0].second] = 0; shark.first = fishes[0].first; shark.second = fishes[0].second; } } }