Submission #1088617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088617		nikd	Toy (CEOI24_toy)	C++17	0 / 100	5 ms	2396 KiB

Main

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

int w,h;
vector<vector<bool>> sol;
vector<string> grid;

inline bool isvalid(int i, int j){
    return i<h&&j<w&& i>=0 && j>= 0 && sol[i][j]==0 && grid[i][j]!='X';
}

int main(){
    cin >> w >> h;
    int K, L; cin >> K >> L;
    int xh, yh, xv, yv; cin >> xh >> yh >> xv >> yv;
    grid.resize(h);
    for(int i = 0; i<h; i++) cin >> grid[i];
    sol.resize(h, vector<bool>(w, 0));

    vector<vector<int>> l(h, vector<int>(w, -1));
    vector<vector<int>> r(h, vector<int>(w, -1));
    vector<vector<int>> t(h, vector<int>(w, -1));
    vector<vector<int>> b(h, vector<int>(w, -1));

    queue<pair<int, int>> q;
    int i_obj, j_obj;
    for(int i = 0; i<h; i++){
        for(int j = 0; j<w; j++){
            if(grid[i][j]=='*'){
                i_obj = i; j_obj = j;
            }
            else if(grid[i][j]=='X'){
                q.push({i, j});
                l[i][j]=0;
                r[i][j]=0;
                t[i][j]=0;
                b[i][j]=0;
                int i2 = i; int j2 = j;
                i2++;
                while(isvalid(i2, j2)){
                    t[i2][j2]=t[i2-1][j2]+1;
                    i2++;
                }
                i2 = i; i2--;
                while(isvalid(i2, j2)){
                    b[i2][j2]=b[i2+1][j2]+1;
                    i2--;
                }
                i2 = i; j2++;
                while(isvalid(i2, j2)){
                    l[i2][j2]=l[i2][j2-1]+1;
                    j2++;
                }
                j2 = j; j2--;
                while(isvalid(i2, j2)){
                    r[i2][j2]=r[i2][j2+1]+1;
                    j2--;
                }
                
            }
        }
    }

    /*while(!q.empty()){
        auto pr = q.front();
        int i_v = pr.first;
        int j_v = pr.second;
        q.pop();
        if(isvalid(i_v+1, j_v)&&t[i_v+1][j_v]==-1&&t[i_v][j_v]!=-1){
            t[i_v+1][j_v] = t[i_v][j_v]+1;
            q.push({i_v+1, j_v});
        }
        if(isvalid(i_v-1, j_v)&&b[i_v-1][j_v]==-1&&b[i_v][j_v]!=-1){
            b[i_v-1][j_v] = b[i_v][j_v]+1;
            q.push({i_v-1, j_v});
        }
        if(isvalid(i_v, j_v+1)&&l[i_v][j_v+1]==-1&&l[i_v][j_v]!=-1){
            l[i_v][j_v+1] = l[i_v][j_v]+1;
            q.push({i_v, j_v+1});
        }
        if(isvalid(i_v, j_v-1)&&r[i_v][j_v-1]==-1&&r[i_v][j_v]!=-1){
            r[i_v][j_v-1] = r[i_v][j_v]+1;
            q.push({i_v, j_v-1});
        }  
    }*/

    for(int i = 0; i<h; i++){
        for(int j = 0; j<w; j++){
            if(t[i][j]==-1) t[i][j]=i+1;
            if(b[i][j]==-1) b[i][j]=h-i;
            if(l[i][j]==-1) l[i][j]=j+1;
            if(r[i][j]==-1) r[i][j]=w-j;

        }
    }


    int i_start = yh; int j_start = xv;

    q.push({i_start, j_start});

    while(!q.empty()){
        auto pr = q.front();
        int i_v = pr.first;
        int j_v = pr.second;
        q.pop();
        if(isvalid(i_v+1, j_v)){
            int l_1 = min(l[i_v][j_v], l[i_v+1][j_v]);
            int r_1 = min(r[i_v][j_v], r[i_v+1][j_v]);
            if(r_1+l_1-1>=K){
                sol[i_v+1][j_v]=1;
                q.push({i_v+1, j_v});
            }
        }
        if(isvalid(i_v-1, j_v)){
            int l_1 = min(l[i_v][j_v], l[i_v-1][j_v]);
            int r_1 = min(r[i_v][j_v], r[i_v-1][j_v]);
            if(r_1+l_1-1>=K){
                sol[i_v-1][j_v]=1;
                q.push({i_v-1, j_v});
            }
        }
        if(isvalid(i_v, j_v+1)){
            int t_1 = min(t[i_v][j_v+1], t[i_v][j_v]);
            int b_1 = min(b[i_v][j_v+1], b[i_v][j_v]);
            if(b_1+t_1-1>=L){
                sol[i_v][j_v+1]=1;
                q.push({i_v, j_v+1});
            }
        }
        if(isvalid(i_v, j_v-1)){
            int t_1 = min(t[i_v][j_v-1], t[i_v][j_v]);
            int b_1 = min(b[i_v][j_v-1], b[i_v][j_v]);
            if(b_1+t_1-1>=L){
                sol[i_v][j_v-1]=1;
                q.push({i_v, j_v-1});
            }
        }
    }

    if(sol[i_obj][j_obj]) cout << "YES\n";
    else cout << "NO\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:141:17: warning: 'i_obj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |     if(sol[i_obj][j_obj]) cout << "YES\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