QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532848#9164. ToyDimash#0 7ms19168kbC++233.0kb2024-08-25 13:17:232024-08-25 13:17:24

Judging History

你现在查看的是最新测评结果

  • [2024-08-25 13:17:24]
  • 评测
  • 测评结果:0
  • 用时:7ms
  • 内存:19168kb
  • [2024-08-25 13:17:23]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 2e3 + 12, MOD = (int)1e9 + 7;
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
int n, m, k, l, x, y;
int a[N][N],ph[N][N],nh[N][N],pv[N][N],nv[N][N];
bool vis[N][N];
bool ok(int X,int Y) {
    return (min(X,Y) >= 1 && X <= n && Y <= m && !a[X][Y]);
}
int inter(int l,int r,int l1,int r1) {
    // cout << l << ' ' << r << ' ' << l1 << ' ' << r1 << '\n';
    return max(0,min(r,r1) - max(l,l1) + 1);
}
void test(){
    cin >> n >> m >> l >> k;
    swap(n,m);
    int x1, y1;
    cin >> y >> x >> y1 >> x1;
    y = y1;
    x++;
    y++;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char t;
            cin >> t;
            if(t == 'X') {
                a[i][j] = 1;
            }
            if(t == '*') {
                x1 = i;
                y1 = j;
            }
            if(a[i][j]) {
                ph[i][j] = j;
            } else {
                ph[i][j] = ph[i][j - 1];
            }
        }
        nh[i][m + 1] = m + 1;
        for(int j = m;j >= 1;j--) {
            if(a[i][j]) {
                nh[i][j] = j;
            } else {
                nh[i][j] = nh[i][j + 1];
            }
        }
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1; j <= n; j++) {
            if(a[j][i]) {
                pv[j][i] = j;
            } else {
                pv[j][i] = pv[j - 1][i];
            }
            // cout << j << ' ' << i << ' ' << pv[j][i] << '\n';   
        }
        nv[n + 1][i] = n + 1;
        for(int j = n; j >= 1; j--) {
            if(a[j][i]) {
                nv[j][i] = j;
            } else {
                nv[j][i] = nv[j + 1][i];
            }
        }
    }
    queue<pair<int,int>> q;
    q.push({x,y});
    vis[x][y] = 1;
    while(!q.empty()) {
        auto [x_,y_] = q.front();
        // cout << x_ << ' ' << y_ << '\n';
        if(x_ == x1 && y_ == y1) {
            cout << "Yes\n";
            return;
        }
        q.pop();
        for(int i = 0; i < 4; i++) {
            int _x = x_ + dx[i],_y = y_ + dy[i];
            if(!ok(_x,_y) || vis[_x][_y]) continue;
            // cout << _x << ' ' << _y << '\n';
            if(x != _x) {
                if(inter(ph[x_][y_] + 1,nh[x_][y_] - 1,ph[_x][_y] + 1,nh[_x][_y] - 1) >= k) {
                    vis[_x][_y] = 1;
                    q.push({_x,_y});
                }
            } else {
                // cout << inter(pv[x_][y_] + 1,nv[x_][y_] - 1,pv[_x][_y] + 1,nv[_x][_y] - 1) << ' ' << "x\n";
                if(inter(pv[x_][y_] + 1,nv[x_][y_] - 1,pv[_x][_y] + 1,nv[_x][_y] - 1) >= l) {
                    vis[_x][_y] = 1;
                    q.push({_x,_y});
                }
            }
        }
    }
    cout << "No\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 14
Accepted
time: 1ms
memory: 8048kb

input:

32 16 23 15
3 8 4 1
................................
................................
................................
................................
................................
*...............................
................................
................................
...................

output:

Yes

result:

ok answer is YES

Test #2:

score: 14
Accepted
time: 1ms
memory: 8120kb

input:

50 50 22 14
26 34 36 33
..................................................
..................................................
..................................................
..................................................
..................................................
........................

output:

Yes

result:

ok answer is YES

Test #3:

score: 14
Accepted
time: 0ms
memory: 8448kb

input:

50 50 50 50
0 18 2 0
..................................................
...............................................X..
..................................................
..................................................
..................................................
...........................

output:

No

result:

ok answer is NO

Test #4:

score: 0
Wrong Answer
time: 2ms
memory: 10160kb

input:

5 47 4 47
1 25 3 0
.X...
.....
.....
.X...
.....
.....
.....
.....
.....
.....
.....
.....
..*..
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
X....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....

output:

No

result:

wrong answer expected YES, found NO

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #89:

score: 9
Accepted
time: 1ms
memory: 8052kb

input:

105 31 8 4
70 27 75 26
.........................................................................................................
.........................................................................................................
....................................................................

output:

Yes

result:

ok answer is YES

Test #90:

score: 9
Accepted
time: 0ms
memory: 17196kb

input:

300 300 4 8
231 246 234 240
...................................................................................................................................................................................................................................................................................

output:

Yes

result:

ok answer is YES

Test #91:

score: 9
Accepted
time: 5ms
memory: 19168kb

input:

300 300 10 10
151 143 155 137
.................................................................................................................................................................................................................................................................................

output:

Yes

result:

ok answer is YES

Test #92:

score: 9
Accepted
time: 0ms
memory: 10780kb

input:

159 68 6 2
95 54 98 54
.........................................................................X.....................................................................................
..........................X..................................................X..........................................

output:

Yes

result:

ok answer is YES

Test #93:

score: 9
Accepted
time: 7ms
memory: 18440kb

input:

300 300 10 10
11 147 12 143
.....................................................................X.................X.......................................*X..............................................X...................................................................................................

output:

Yes

result:

ok answer is YES

Test #94:

score: 9
Accepted
time: 6ms
memory: 18316kb

input:

300 300 10 10
289 237 298 236
.........................................................................................X.......................................................................................................................................................................................

output:

Yes

result:

ok answer is YES

Test #95:

score: 9
Accepted
time: 3ms
memory: 11412kb

input:

277 111 6 9
109 9 112 5
...................X..XX...........X.......X..................X...X.......X........X......X...........X....................X.......................X..X..X.........XX...................X..............X..........X..................X................X...................X............

output:

No

result:

ok answer is NO

Test #96:

score: 0
Wrong Answer
time: 3ms
memory: 17696kb

input:

300 300 6 6
126 5 131 1
.......X............XX..............X...X....XX..........X..X........X.X...X...........X.................X...............X..............X.....XX.............X....................................XX....X................X........X...................X.....X..........................

output:

Yes

result:

wrong answer expected NO, found YES

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%