[白俊1584]ゲーム

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.結果