| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1045688 |
2024-08-06T06:58:24 Z |
alex_2008 |
Toy (CEOI24_toy) |
C++14 |
|
1 ms |
6488 KB |
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
typedef long long ll;
using namespace std;
const int N = 1510;
char a[N][N];
bool used[N][N];
int tp[N][N];
int dwn[N][N];
int lft[N][N];
int rght[N][N];
int w, h, k, l;
int cnt(int x1, int y1, int x2, int y2) {
return a[x2][y2] - a[x1][y2] - a[x2][y1] + a[x1][y1];
}
pair<int, int> vertical_range(int x, int y) {
if (tp[x][y] + dwn[x][y] <= l) return { 1, 0 };
int r_min = x - tp[x][y] + 1;
int r_mx = x + dwn[x][y] - l;
return make_pair(r_min, r_mx);
}
pair<int, int> horizontal_range(int x, int y) {
if (lft[x][y] + rght[x][y] <= k) return { 1, 0 };
int c_min = x - lft[x][y] + 1;
int c_mx = x + rght[x][y] - k;
return make_pair(c_min, c_mx);
}
bool intersect(pair<int, int> x, pair<int, int> y) {
pair<int, int> c = make_pair(max(x.first, y.first), min(x.second, y.second));
if (c.first > c.second) return false;
return true;
}
bool ch(int x, int y) {
if ((tp[x][y] + dwn[x][y]) > l && (lft[x][y] + rght[x][y]) > k) return true;
return false;
}
int main() {
cin >> w >> h >> k >> l;
int xh, yh, xv, yv;
cin >> xh >> yh >> xv >> yv;
xh++; xv++; yh++; yv++;
swap(xh, yh); swap(xv, yv);
//cout << xh << " " << yh << " " << xv << " " << yv << "\n";
int fx = -1, fy = -1;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> a[i][j];
if (a[i][j] == '*') {
fx = i;
fy = j;
}
}
}
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (a[i][j] == 'X') {
lft[i][j] = 0;
tp[i][j] = 0;
}
else {
lft[i][j] = lft[i][j - 1] + 1;
tp[i][j] = tp[i - 1][j] + 1;
}
lft[i][j] = min(lft[i][j], k);
tp[i][j] = min(tp[i][j], l);
}
}
for (int i = h; i >= 1; i--) {
for (int j = w; j >= 1; j--) {
if (a[i][j] == 'X') {
rght[i][j] = 0;
dwn[i][j] = 0;
}
else {
rght[i][j] = rght[i][j + 1] + 1;
dwn[i][j] = dwn[i + 1][j] + 1;
}
rght[i][j] = min(rght[i][j], k);
dwn[i][j] = min(dwn[i][j], l);
}
}
used[xh][yv] = true;
queue <pair<int, int>> Q;
Q.push({ xh, yv });
while (!Q.empty()) {
int x = Q.front().first, y = Q.front().second; Q.pop();
//cout << "? " << x << " " << y << "\n";
if (x > 1) {
if (intersect(vertical_range(x, y), vertical_range(x - 1, y)) && ch(x - 1, y)) {
if (!used[x - 1][y]) {
used[x - 1][y] = true;
Q.push({ x - 1, y });
}
}
}
if (x < h) {
if (intersect(vertical_range(x, y), vertical_range(x + 1, y)) && ch(x + 1, y)) {
if (!used[x + 1][y]) {
used[x + 1][y] = true;
Q.push({ x + 1, y });
}
}
}
if (y > 1) {
if (intersect(horizontal_range(x, y), horizontal_range(x, y - 1)) && ch(x, y - 1)) {
if (!used[x][y - 1]) {
used[x][y - 1] = true;
Q.push({ x, y - 1 });
}
}
}
if (y < w) {
if (intersect(horizontal_range(x, y), horizontal_range(x, y + 1)) && ch(x, y + 1)) {
if (!used[x][y + 1]) {
used[x][y + 1] = true;
Q.push({ x, y + 1 });
}
}
}
}
if (used[fx][fy]) cout << "Yes\n";
else cout << "No\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
