제출 #1280282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280282		khanhphucscratch	Toy (CEOI24_toy)	C++20	0 / 100	1630 ms	929092 KiB

Main

#include<bits/stdc++.h>
using namespace std;
vector<int> ad[2250005];
int n, m, le[1505][1505], ri[1505][1505], up[1505][1505], down[1505][1505];
char a[1505][1505];
bool visited[2250005];
int tran(int r, int c)
{
    return r*m+c;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int l1, l2, r1, c1, r2, c2;
    cin>>m>>n>>l1>>l2>>c1>>r1>>c2>>r2;
    int start_node = tran(r1, c2), target_node;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin>>a[i][j];
            if(a[i][j] == '*') target_node = tran(i, j);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 'X') le[i][j] = 1e9;
            else if(j == 0) le[i][j] = j;
            else le[i][j] = min(le[i][j-1], j);
        }
        for(int j = m-1; j >= 0; j--){
            if(a[i][j] == 'X') ri[i][j] = 1e9;
            else if(j == m-1) ri[i][j] = j;
            else ri[i][j] = max(ri[i][j+1], j);
        }
    }
    for(int j = 0; j < m; j++){
        for(int i = 0; i < n; i++){
            if(a[i][j] == 'X') up[i][j] = 1e9;
            else if(i == 0) up[i][j] = i;
            else up[i][j] = min(up[i-1][j], i);
        }
        for(int i = n-1; i >= 0; i--){
            if(a[i][j] == 'X') down[i][j] = 1e9;
            else if(i == n-1) down[i][j] = i;
            else down[i][j] = min(down[i+1][j], i);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(i > 0 && min(ri[i][j], ri[i-1][j]) - max(le[i][j], le[i-1][j]) + 1 >= l1){
                int u = tran(i, j), v = tran(i-1, j);
                ad[u].push_back(v); ad[v].push_back(u);
            }
            if(j > 0 && min(down[i][j], down[i][j-1]) - max(up[i][j], up[i][j-1]) + 1 >= l2){
                int u = tran(i, j), v = tran(i, j-1);
                ad[u].push_back(v); ad[v].push_back(u);
            }
        }
    }
    queue<int> w; w.push(start_node);
    while(w.size() > 0){
        int u = w.front(); w.pop(); visited[u] = 1;
        for(int v : ad[u]) if(visited[v] == 0) w.push(v);
    }
    if(visited[target_node] == 1) 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