백준(BOJ) 15805 영우의 기숙사 청소 **

#BFS

기본적인 BFS문제에서 짝수시간과 홀수시간을 분리하여 visit을 확인하면된다.

흠.... 생각보다 실수를 많이해서 여러번 제출하였다....

#include <iostream>
#include <algorithm>
#include <queue>
#define MAX 305
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

struct st{
    int turn;
    int x;
    int y;
};
int a,b,c,d,x,y;
int dy[8]={2,2,-2,-2,1,-1,1,-1},dx[8]={1,-1,1,-1,2,2,-2,-2};
queue<st> q;
bool tf[2][MAX][MAX];

int main()
{
    scanf("%d%d%d%d",&a,&b,&c,&d);
    for(int i=0;i<b;i++)
    {
        scanf("%d%d",&x,&y);
        st s={0,x,y};
        q.push(s);
        tf[0][y][x]=true;
    }
    for(int i=0;i<d;i++)
    {
        while(!q.empty()&&q.front().turn==i%2)
        {
            st tmp = q.front();
            q.pop();
            for(int k=0;k<8;k++)
            {
                int ty=tmp.y+dy[k],tx=tmp.x+dx[k];
                if(1<=ty&&ty<=a&&1<=tx&&tx<=a)
                {
                    if(tf[(i+1)%2][ty][tx]==false)
                    {
                        st s={(i+1)%2,x,y};
                        q.push(s);
                        tf[(i+1)%2][ty][tx]=true;
                    }
                }
            }
        }
    }
    for(int i=0;i<c;i++)
    {
        scanf("%d%d",&x,&y);
        if(tf[d%2][y][x]==true)
        {
            printf("YES");
            return 0;
        }
    }
    printf("NO");
    return 0;
}