1227. 그녀의 마음

업데이트 시간 : 2023-04-06 15:00:22 +0000

[Platinum II] 그녀의 마음 - 1227

문제 링크

성능 요약

메모리: 17696 KB, 시간: 140 ms

분류

수학, 그래프 이론, 그래프 탐색, 애드 혹, 너비 우선 탐색, 많은 조건 분기

문제 설명

김상근과 김정인이 그녀의 마음을 얻기 위해 경쟁을 벌이고 있다. 그들은 다음과 같은 방법으로 승자를 결정하기로 했다.

무한한 크기의 2차원 평면에 어떤 지점에서 그녀가 걷기 시작한다. 그리고 그녀는 상, 하, 좌, 우 4방향으로 걸어갈 수 있는데 한번 걸어갈때마다 마음이 바뀐다. 즉, 상근이를 좋아하고 있었다면 정인이를 좋아하게 되고 정인이를 좋아하고 있었다면 상근이를 좋아하게 된다. 시작점에서는 그녀가 상근이를 좋아한다고 한다. 또한 2차원 좌표판 중에는 장애물이 있는 곳이 있어서 그런 곳은 지나가지 못한다고 하자. 이때 그녀는 그 시작점에서 (0, 0)까지 장애물을 피하여 최단거리로 걸어온다고 가정한다.

그녀가 무한한 체력을 가진 것은 아니므로 그녀가 걷는 걸음수를 S걸음 이하로 제한할 때 2차원 좌표 중 최종적으로 그녀가 (0, 0)에 왔을때 상근이를 좋아하게 될 시작점의 개수와 정인이를 좋아하게 될 시작점의 개수를 구하라.

입력

첫 줄에는 장애물의 개수 B와 걸음수 S가 주어진다. (1<=B<=10000, 1<=S<=10000000) 그리고 다음 B줄에는 장애물의 좌표가 주어진다. 장애물의 x, y값의 절댓값은 1000보다 작다고 하자.

출력

상근이를 좋아하게 될 시작점의 개수와 정인이를 좋아하게 될 시작점의 개수를 출력하라.

💡 Solutions

📄 그녀의 마음.cc

#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;

#define MAX 1000

void edge(int x, int y, int d, int K, long long res[2])
{
   res[(x+y)%2]   += (K-d)/2;
   res[(x+y+1)%2] += (K-d+1)/2;
}

void corner(int x, int y, int d, int K, long long res[2])
{
   long long n;
   n = (K-d)/2;   res[(x+y)%2]   += n*n;
   n = (K-d-1)/2; res[(x+y+1)%2] += n*(n+1);
}

int main()
{
   int P, K;
   scanf( "%d%d", &P, &K );
   ++K;

   static int d[2*MAX+3][2*MAX+3];
   int x0=MAX+1, y0=MAX+1;
   int
      minx = x0, maxx = x0,
      miny = y0, maxy = y0;
   
   for ( int i=0; i<P; ++i ) {
      int x, y;
      scanf( "%d%d", &x, &y );
      x += x0; y += y0;
      minx = min( minx, x ); maxx = max( maxx, x );
      miny = min( miny, y ); maxy = max( maxy, y );
      d[x][y] = -1;
   }
   --minx; --miny;
   ++maxx; ++maxy;

   long long res[2] = { 0, 0 };

   queue<int> qx, qy;
   d[x0][y0] = 1;
   qx.push(x0); qy.push(y0); 
   while ( !qx.empty() ) {
      int x = qx.front(); qx.pop();
      int y = qy.front(); qy.pop();

      ++res[(x+y)%2];
      if ( d[x][y] == K ) {
         continue;
      }
      if ( x == minx || x == maxx ) edge(x, y, d[x][y], K, res);
      if ( y == miny || y == maxy ) edge(x, y, d[x][y], K, res);
      
      static const int dx[] = { -1, 0, 1, 0 };
      static const int dy[] = { 0, 1, 0, -1 };
      for ( int dir=0; dir<4; ++dir ) {
         int nx = x + dx[dir], ny = y + dy[dir];
         if ( nx < minx || nx > maxx || ny < miny || ny > maxy || d[nx][ny] != 0 ) continue;

         d[nx][ny] = d[x][y] + 1;
         qx.push( nx ); qy.push( ny );
      }
   }

   if ( d[minx][miny] > 0 ) corner( minx, miny, d[minx][miny], K, res );
   if ( d[minx][maxy] > 0 ) corner( minx, maxy, d[minx][maxy], K, res );
   if ( d[maxx][miny] > 0 ) corner( maxx, miny, d[maxx][miny], K, res );
   if ( d[maxx][maxy] > 0 ) corner( maxx, maxy, d[maxx][maxy], K, res );

   cout << res[0] << ' ' << res[1] << endl;

   return 0;
}