[白俊1584]ゲーム
5543 ワード
A.方法
優先キューのBFSで問題を解決しました.これは失われた生命値を最小限に抑えるためのpop探索を継続する方法である.問題解決後に検索すると,この解法は「0−1 BFS」であることが分かった.
B.実施
class cmp {
public:bool operator ()(const vector& p1, const vector& p2) {
if(p1[2] < p2[2])
return false;
else
return true;
}
};
「これはpopの比較部分を続けるためで、この部分は失われた生命の最小値です.」0-1 BFSではデータ構造を使用し、失われた生命が現在よりも大きい場合はdequeのpush backを使用し、同じpush frontを使用しても失われた生命値は減少しません.△減少してもpush frontは次のpopの目標になるので問題ありません.
C.コード
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
int T, N, M;
int table[501][501];
bool visit[501][501];
int answer;
//queue<vector<int>> q;
class cmp {
public:bool operator ()(const vector<int>& p1, const vector<int>& p2) {
if(p1[2] < p2[2])
return false;
else
return true;
}
};
priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
void bfs() {
while(!pq.empty()) {
int x = pq.top()[0];
int y = pq.top()[1];
int z = pq.top()[2];
pq.pop();
//cout << x << " " << y << " " << z << endl;
if(x == 500 && y == 500) {
if(z < answer)
answer = z;
continue;
}
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 0 && nx <= 500 && ny >= 0 && ny <= 500 && table[nx][ny] != 2 && !visit[nx][ny]) {
if(table[nx][ny] == 0) {
visit[nx][ny] = true;
pq.push(vector<int> {nx, ny, z});
}
else if(table[nx][ny] == 1) {
visit[nx][ny] = true;
pq.push(vector<int> {nx, ny, z+1});
}
else {}
}
}
}
}
int main() {
//scanf("%d", &T);
T = 1;
for(int tc = 0; tc < T; tc++) {
scanf("%d", &N);
memset(table, 0, sizeof(int)*501*501);
memset(visit, 0, sizeof(bool) * 501 *501);
answer = 9999999;
for(int i = 0; i < N; i++) {
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
if(a > c) {
int tmp = a;
a = c;
c = tmp;
}
if(b > d) {
int tmp = b;
b = d;
d = tmp;
}
for(int x = a; x <= c; x++) {
for(int y = b; y <= d; y++) {
table[x][y] = 1;
}
}
}
scanf("%d", &M);
for(int i = 0; i < M; i++) {
int a, b, c, d;
scanf("%d %d %d %d", &a, &b, &c, &d);
if(a > c) {
int tmp = a;
a = c;
c = tmp;
}
if(b > d) {
int tmp = b;
b = d;
d = tmp;
}
for(int x = a; x <= c; x++) {
for(int y = b; y <= d; y++) {
table[x][y] = 2;
}
}
}
visit[0][0] = true;
pq.push(vector<int> {0,0,0});
bfs();
if(answer == 9999999)
cout << "-1" << endl;
else
cout << answer << endl;
}
return 0;
}D.結果
Reference
この問題について([白俊1584]ゲーム), 我々は、より多くの情報をここで見つけました https://velog.io/@pamrk2002/백준-1584-게임テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol