Submission #1069884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069884		Benmath	Toy (CEOI24_toy)	C++14	0 / 100	0 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n , m, k, l;
    cin >> n >> m >> k >> l;
     swap(m,n);
     int xh,yh,xv,yv;
     cin >> xh >> yh >> xv >> yv;
    
     swap(xh,yh);
     swap(xv,yv);
     int cx = xh;
     int cy = yv;
     
     int locx = -1;
     int locy = -1;
     queue<pair<int,int>>q;
     char mat[n][m];
     int vis[n][m];
     int preth_red[n][m];
     int next_red[n][m];
     int preth_kol[n][m];
     int next_kol[n][m];
     for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
             cin >> mat[i][j];    vis[i][j] = 0;
             if(mat[i][j] == '*'){
                 locx = i;
                 locy = j;
             
             }
            if(j == 0){
                if(mat[i][j] != 'X'){
                    preth_red[i][j] = j;
                }
            }else{
                if(mat[i][j] != 'X'){
                   if(mat[i][j - 1] == 'X'){
                       preth_red[i][j] = j;
                   }else{
                       preth_red[i][j] = preth_red[i][j - 1];
                   }
                }
            }
         }
         for(int j = (m - 1); j >= 0; j --){
             if(j == (m - 1)){
                if(mat[i][j] != 'X'){
                    next_red[i][j] = j;
                }
            }else{
                if(mat[i][j] != 'X'){
                   if(mat[i][j + 1] == 'X'){
                       next_red[i][j] = j;
                   }else{
                      next_red[i][j] = next_red[i][j + 1];
                   }
                }
            }
         }
     }
     for(int j = 0; j < m; j++){
         for(int i = 0; i < n; i++){
              if(i == 0){
                if(mat[i][j] != 'X'){
                    preth_kol[i][j] = i;
                }
            }else{
                if(mat[i][j] != 'X'){
                   if(mat[i - 1][j] == 'X'){
                       preth_kol[i][j] = i;
                   }else{
                       preth_kol[i][j] = preth_kol[i - 1][j];
                   }
                }
            }
         }
         for(int i = (n - 1); i >= 0; i --){
              if(i == (n - 1)){
                if(mat[i][j] != 'X'){
                    next_kol[i][j] = i;
                }
            }else{
                if(mat[i][j] != 'X'){
                   if(mat[i + 1][j] == 'X'){
                       next_kol[i][j] = i;
                   }else{
                         next_kol[i][j] = next_kol[i + 1][j];
                   }
                }
            }
         }
     }
    // cout << locx << " " << locy << endl;
     q.push({cx,cy});
     vis[cx][cy]++;
     while(!q.empty()){
         pair<int,int>p =q.front();
         q.pop();
         int x = p.first;
         int y = p.second;
        
         if(x == locx and y == locy){
             cout << "YES";
             return 0;
         }
         if((y + 1) < m){
             if(vis[x][y + 1] == 0){
             if(mat[x][y + 1] != 'X'){
                 int ro1 = max(preth_kol[x][y],preth_kol[x][y + 1]);
                 int ro2 = min(next_kol[x][y],next_kol[x][y + 1]);
                 if((ro2 - ro1 + 1) >= l){
                    
                     vis[x][y + 1] ++;
                     q.push({x, y + 1});
                 }
             }
             }
         }
         if((y - 1) > 0){
             if(vis[x][y  - 1] == 0){
             if(mat[x][y - 1] != 'X'){
                 int ro1 = max(preth_kol[x][y],preth_kol[x][y - 1]);
                 int ro2 = min(next_kol[x][y],next_kol[x][y - 1]);
                 if((ro2 - ro1 + 1) >= l){
                     vis[x][y - 1] ++;
                     q.push({x, y - 1});
                 }
             }
             }
         }
         if((x + 1) < n){
             if(vis[x + 1][y] == 0){
                 int ro1 = max(preth_red[x][y], preth_red[x + 1][y]);
                 int ro2 = min(next_red[x][y], next_red[x + 1][y]);
                 if((ro2 - ro1 + 1) >= k){
                     vis[x + 1][y] ++;
                     q.push({x + 1, y});
                 }
             }
         }
         if((x - 1) > 0){ 
             if(vis[x - 1][y] == 0){
                 int ro1 = max(preth_red[x][y], preth_red[x-1][y]);
                 int ro2 = min(next_red[x][y], next_red[x - 1][y]);
                 if((ro2 - ro1 + 1) >= k){
                     vis[x - 1][y] ++;
                     q.push({x - 1, y});
                 }
             }
         }
     }
     cout << "NO";
}

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