Submission #1220974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220974		KindaGoodGames	Toy (CEOI24_toy)	C++20	0 / 100	0 ms	328 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define tiiii tuple<int,int,int,int>

int main(){
    int n, m, w, h;
    cin >> n >> m >> w >> h;

    int XH, YH, XV, YV;
    cin >>XH >> YH >> XV >> YV;

    vector<vector<char>> grid(n, vector<char>(m));

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> validH(n, vector<bool>(m));
    vector<vector<bool>> validV(n, vector<bool>(m));
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= m-w; j++){
            bool valid = true;
            for(int k = j; k < j+w; k++){
                if(grid[i][k] == 'X'){
                    valid = false;
                    break;
                }
            }
            validH[i][j] = valid;
        }
    }
    for(int i = 0; i < n-h; i++){
        for(int j = 0; j < m; j++){
            bool valid = true;
            for(int k = i; k < i+h; k++){
                if(grid[k][j] == 'X'){
                    valid = false;
                    break;
                }
            }
            validV[i][j] = valid;
        }
    }


    set<tiiii> vis;

    queue<tiiii> q;
    q.push({XH, YH, XV, YV});

    bool res = false;

    while(q.size()){
        if(res) break;
        int xh, yh, xv, yv;
        tie(xh, yh, xv, yv) = q.front(); q.pop();

        auto push = [&](int x1, int y1, int x2, int y2){
            if(x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0) return;
            if(x1 >=m || y1 >= n || x2 >=m || y2 >= n) return;
        
            if(!validH[y1][x1]) return;
            if(!validV[y2][x2]) return;

            if(vis.count({x1,y1,x2,y2})) return;
            if(grid[y1][x2] == '*'){
                res = true;
                return;
            }
            vis.insert({x1,y1,x2,y2});
            q.push({x1,y1,x2,y2});
        };

        push(xh+1,yh,xv,yv);
        push(xh,yh+1,xv,yv);
        push(xh,yh,xv+1,yv);
        push(xh,yh,xv,yv+1);

        push(xh-1,yh,xv,yv);
        push(xh,yh-1,xv,yv);
        push(xh,yh,xv-1,yv);
        push(xh,yh,xv,yv-1);
    }


    if(res){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27