제출 #599962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
599962		Piokemon	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	1 ms	468 KiB

dango_maker

 #include <bits/stdc++.h>
using namespace std;

int d[2][2] = {{1,0},{0,1}};
string plansza[1009];
int i_prze[1009][1009][4];
deque<pair<pair<int,int>,int>> wybierz[4];
int n,m;

bool check(int x, int y, int z){
    if (x<1 || x>n || y<1 || y>m || x+d[z][0]*2<1 || x+d[z][0]*2>n || y+d[z][1]*2<1 || y+d[z][1]*2>m){
        return 0;
    }
    if ((plansza[x][y] == 'R') && (plansza[x + d[z][0]][y + d[z][1]] == 'G') && (plansza[x + d[z][0]*2][y + d[z][1]*2] == 'W')){
        return 1;
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int odp = 0,p=0,x,y,z;
    pair<pair<int,int>,int> ter;
    cin >> n >> m;
    for (int x=1;x<=n;x++){
        cin >> plansza[x];
        plansza[x] = '#' + plansza[x];
    }
    for (x=1;x<=n;x++){
        for (y=1;y<=m;y++){
            for (z=0;z<2;z++){
                if (!check(x,y,z)){
                    i_prze[x][y][z] = -1;
                    continue;
                }
                i_prze[x][y][z] = 0;
                if (z==0){
                    if (check(x,y,1)){
                        i_prze[x][y][z] += 1;
                    }
                    if (check(x+1, y-1, 1)){
                        i_prze[x][y][z] += 1;
                    }
                    if (check(x+2, y-2, 1)){
                        i_prze[x][y][z] += 1;
                    }
                }
                else{
                    if (check(x,y,0)){
                        i_prze[x][y][z] += 1;
                    }
                    if (check(x-1, y+1, 0)){
                        i_prze[x][y][z] += 1;
                    }
                    if (check(x-2, y+2, 0)){
                        i_prze[x][y][z] += 1;
                    }
                }
                wybierz[i_prze[x][y][z]].push_back({{x,y},z});
            }
        }
    }
    while(p<4){
        if (wybierz[p].empty()){
            p += 1;
            continue;
        }
        ter = wybierz[p].front();
        wybierz[p].pop_front();
        x = ter.first.first; y = ter.first.second; z = ter.second;
        if (!check(x,y,z) || i_prze[x][y][z] != p){
            continue;
        }
        odp += 1;
        plansza[x][y] = 'X';
        plansza[x+d[z][0]][y+d[z][1]] = 'X';
        plansza[x + d[z][0]*2][y + d[z][1]*2] = 'X';
        if (check(x,y,!z)){
            if (check(x+1,y-1,z)){
                i_prze[x+1][y-1][z] -= 1;
                wybierz[i_prze[x+1][y-1][z]].push_back({{x+1,y-1},z});
                p = min(p, i_prze[x+1][y-1][z]);
            }
            if (check(x+2,y-2,z)){
                i_prze[x+2][y-2][z] -= 1;
                wybierz[i_prze[x+2][y-2][z]].push_back({{x+2,y-2},z});
                p = min(p, i_prze[x+2][y-2][z]);
            }
        }
        if (check(x-1,y+1,!z)){
            if (check(x+1,y-1,z)){
                i_prze[x+1][y-1][z] -= 1;
                wybierz[i_prze[x+1][y-1][z]].push_back({{x+1,y-1},z});
                p = min(p, i_prze[x+1][y-1][z]);
            }
            if (check(x-1,y+1,z)){
                i_prze[x-1][y+1][z] -= 1;
                wybierz[i_prze[x-1][y+1][z]].push_back({{x-1,y+1},z});
                p = min(p, i_prze[x-1][y+1][z]);
            }
        }
        if (check(x-2,y+2,!z)){
            if (check(x-1,y+1,z)){
                i_prze[x-1][y+1][z] -= 1;
                wybierz[i_prze[x-1][y+1][z]].push_back({{x-1,y+1},z});
                p = min(p, i_prze[x-1][y+1][z]);
            }
            if (check(x-2,y+2,z)){
                i_prze[x-2][y+2][z] -= 1;
                wybierz[i_prze[x-2][y+2][z]].push_back({{x-2,y+2},z});
                p = min(p, i_prze[x-2][y+2][z]);
            }
        }
    }
    cout << odp << "\n";
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67