白駿16920:拡張ゲーム
拡張ゲーム
白駿16920号:拡張ゲーム
アイデア
bfsは所定の回数でしか行えません.プレイヤーは1番から9番まで、それぞれキューを作成し、それぞれbfsを行います.
コード#コード#
#include <bits/stdc++.h>
using namespace std;
int N, M, P;
int sn[10];
int sc[10];
int arr[1000][1000];
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
bool check_safe(int y, int x) {
return (y >= 0 && y < N && x >= 0 && x < M);
}
bool bfs(int player, queue<pair<int, int>> &q) {
int cnt = sn[player];
while (cnt--) {
if (q.empty()) return false;
int sz = q.size();
while (sz--) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (!check_safe(ny, nx)) continue;
else if (arr[ny][nx] != 0) continue;
else {
arr[ny][nx] = player;
sc[player]++;
q.push({ny, nx});
}
}
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<queue<pair<int, int>>> v(10);
char ch;
cin >> N >> M >> P;
for (int p = 1; p <= P; p++) {
cin >> sn[p];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> ch;
if (ch == '.') arr[i][j] = 0;
else if (ch == '#') arr[i][j] = -1;
else {
int player = ch - '0';
arr[i][j] = player;
sc[player]++;
v[player].push({i, j});
}
}
}
bool sw = true;
while (sw) {
sw = false;
for (int i = 1; i <= P; i++) {
if (bfs(i, v[i])) sw = true;
}
}
for (int i = 1; i <= P; i++) {
cout << sc[i] << ' ';
}
return 0;
}
おしゃべり
優先順位で作ればいいんですよね?やっているうちにあきらめて、Qをいくつか書きました.
Reference
この問題について(白駿16920:拡張ゲーム), 我々は、より多くの情報をここで見つけました
https://velog.io/@ks1ksi/백준-16920-확장-게임
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <bits/stdc++.h>
using namespace std;
int N, M, P;
int sn[10];
int sc[10];
int arr[1000][1000];
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
bool check_safe(int y, int x) {
return (y >= 0 && y < N && x >= 0 && x < M);
}
bool bfs(int player, queue<pair<int, int>> &q) {
int cnt = sn[player];
while (cnt--) {
if (q.empty()) return false;
int sz = q.size();
while (sz--) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (!check_safe(ny, nx)) continue;
else if (arr[ny][nx] != 0) continue;
else {
arr[ny][nx] = player;
sc[player]++;
q.push({ny, nx});
}
}
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
vector<queue<pair<int, int>>> v(10);
char ch;
cin >> N >> M >> P;
for (int p = 1; p <= P; p++) {
cin >> sn[p];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> ch;
if (ch == '.') arr[i][j] = 0;
else if (ch == '#') arr[i][j] = -1;
else {
int player = ch - '0';
arr[i][j] = player;
sc[player]++;
v[player].push({i, j});
}
}
}
bool sw = true;
while (sw) {
sw = false;
for (int i = 1; i <= P; i++) {
if (bfs(i, v[i])) sw = true;
}
}
for (int i = 1; i <= P; i++) {
cout << sc[i] << ' ';
}
return 0;
}
Reference
この問題について(白駿16920:拡張ゲーム), 我々は、より多くの情報をここで見つけました https://velog.io/@ks1ksi/백준-16920-확장-게임テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol