| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1045752 | VahanAbraham | Toy (CEOI24_toy) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <bitset>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <cassert>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout);
ll gcd(ll a, ll b)
{
if (a == 0 || b == 0) {
return max(a, b);
}
if (a <= b) {
return gcd(a, b % a);
}
else {
return gcd(a % b, b);
}
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
const int N = 503;
const ll oo = 100000000000000000, MOD = 1000000007;
struct cord {
int x, y;
};
char grid[N][N];
bool ok[N][N][N][N], normalahor[N][N], normalaver[N][N];
int w, h, k, l, xend, yend;
int dxhor[3] = { 1,-1,0 };
int dxver[3] = { 1,-1,0 };
int dyhor[3] = { 1,-1,0 };
int dyver[3] = { 1,-1,0 };
queue<pair<cord, cord>> q;
pair<int, int> hatvumen(cord hor, cord ver) {
for (int i = ver.x; i <= ver.x; ++i) {
if (hor.y >= ver.y && hor.y <= ver.y + l - 1 && i >=hor.x && i<=hor.x+k-1) {
return { i,hor.y };
}
}
return{ -1,-1 };
}
bool mejnahor(cord hor) {
if (hor.x >= 0 && hor.x + k - 1 <= w - 1 && hor.y >= 0 && hor.y <= h - 1) {
return true;
}
return false;
}
bool mejnaver(cord ver) {
if (ver.x >= 0 && ver.x <= w - 1 && ver.y >= 0 && ver.y+l-1 <= h - 1) {
return true;
}
return false;
}
bool normalhor(cord hor) {
for (int i = hor.x; i <= hor.x + k - 1; ++i) {
if (grid[hor.y][i] == 'X') {
return false;
}
}
return true;
}
bool normalver(cord ver) {
for (int i = ver.y; i <= ver.y + l - 1; ++i) {
if (grid[i][ver.x] == 'X') {
return false;
}
}
return true;
}
bool stug(cord hor1, cord ver1) {
if (mejnahor(hor1) == 1 && mejnaver(ver1) == 1 && normalahor[hor1.x][hor1.y] == 1 && normalaver[ver1.x][ver1.y] == 1) {
pair<int, int> p = hatvumen(hor1, ver1);
if (p.fr == xend && p.sc == yend){
return true;
}
else {
if (p.fr != -1) {
if (ok[hor1.x][hor1.y][ver1.x][ver1.y] != 1) {
ok[hor1.x][hor1.y][ver1.x][ver1.y] = 1;
q.push({ hor1,ver1 });
return false;
}
return false;
}
return false;
}
return false;
}
return false;
}
void solve() {
cin >> w >> h >> k >> l;
int xh, yh, xv, yv;
cin >> xh >> yh >> xv >> yv;
cord hor, ver;
hor.x = xh;
hor.y = yh;
ver.x = xv;
ver.y = yv;
ok[hor.x][hor.y][ver.x][ver.y] = 1;
q.push({ hor,ver });
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> grid[i][j];
if (grid[i][j] == '*') {
xend = j, yend = i;
}
}
}
/*cout << xend << " " << yend << endl;
cord vv;
vv.x = 1, vv.y = 0;
cout << normalver(vv) << endl;*/
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cord yy;
yy.x = j, yy.y = i;
if (mejnaver(yy)) {
normalaver[j][i] = normalver(yy);
}
if (mejnahor(yy)) {
normalahor[j][i] = normalhor(yy);
}
}
}
while (q.empty() != 1) {
hor = q.front().fr;
ver = q.front().sc;
//cout << hor.x << " " << hor.y << " " << ver.x << " " << ver.y << endl;
q.pop();
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cord hor1 = hor, ver1 = ver;
hor1.x += dxhor[i];
ver1.x += dxver[j];
if (stug(hor1, ver1)) {
//cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
cout << "YES" << endl;
return;
}
}
for (int j = 0; j < 3; ++j) {
cord hor1 = hor, ver1 = ver;
hor1.x += dxhor[i];
ver1.y += dyver[j];
if (stug(hor1, ver1)) {
//cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
cout << "YES" << endl;
return;
}
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cord hor1 = hor, ver1 = ver;
hor1.y += dyhor[i];
ver1.x += dxver[j];
if (stug(hor1, ver1)) {
//cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
cout << "YES" << endl;
return;
}
}
for (int j = 0; j < 3; ++j) {
cord hor1 = hor, ver1 = ver;
hor1.y += dyhor[i];
ver1.y += dyver[j];
if (stug(hor1, ver1)) {
//cout << hor1.x << " " << hor1.y << " " << ver1.x << " " << ver1.y << endl;
cout << "YES" << endl;
return;
}
}
}
}
cout << "NO" << endl;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//US
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
}