제출 #1140592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140592		KaleemRazaSyed	Toy (CEOI24_toy)	C++20	100 / 100	310 ms	252320 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 1500 + 10;
int W, H, K, L;
int xh, yh, xv, yv;
string s[N];
bool seen[N][N];
int Left[N][N], Right[N][N], Up[N][N], Down[N][N];
bool ok = false;

// each cordinate is like (y, x) = (r, c)

// r < H , c < W

bool valid(int r, int c) {
  return (0 <= r && r < H) && (0 <= c && c < W) && (s[r][c] != 'X');
}

bool Edge(int r1, int c1, int r2, int c2)
{
  if(r1 == r2) // vertical line shifting --> up and down
    return min(Up[r1][c1], Up[r2][c2]) + min(Down[r1][c1], Down[r2][c2]) + 1 >= L;
  else // horizontal line shifting ---> left and right
    return min(Left[r1][c1], Left[r2][c2]) + min(Right[r1][c1], Right[r2][c2]) + 1 >= K;
}

void dfs(int r, int c)
{
  int dr[] = {1, -1, 0, 0};

  if(s[r][c] == '*')
    ok = true;
  
  seen[r][c] = true;
  
  for(int i = 0; i < 4; i ++)
    {
      int nr = r + dr[i], nc = c + dr[3 - i];
      if(valid(nr, nc) && Edge(r, c, nr, nc) && !seen[nr][nc])
	dfs(nr, nc);
    }
}

int main()
{

  cin >> W >> H >> K >> L;
  cin >> xh >> yh >> xv >> yv;

  for(int i = 0; i < H; i ++)
    cin >> s[i];

  // Left
  for(int i = 0; i < H; i ++)
    for(int j = 1; j < W; j++)
      if(valid(i, j - 1))
	Left[i][j] = Left[i][j - 1] + 1;

  // Right
  for(int i = 0; i < H; i ++)
    for(int j = W - 2; j >= 0; j--)
      if(valid(i, j + 1))
	Right[i][j] = Right[i][j + 1] + 1;

  // Up
  for(int i = 1; i < H; i ++)
    for(int j = 0; j < W; j++)
      if(valid(i - 1, j))
	Up[i][j] = Up[i - 1][j] + 1;

  // Down
  for(int i = H - 2; i >= 0; i--)
    for(int j = 0; j < W; j++)
      if(valid(i + 1, j))
	Down[i][j] = Down[i + 1][j] + 1;
  
  dfs(yh, xv);
  
  cout << (ok ? "YES" : "NO") << endl;
  return 0;
}

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