경로 (path) 문제 풀이

제목 설명
r * c 의 지도 가 있 습 니 다. 왼쪽 경계 와 오른쪽 경 계 를 붙 여서 하나의 원기둥 을 만 듭 니 다. 지금 은 그 중의 칸 을 계속 파 야 합 니 다. 항상 맨 위 에서 맨 아래 까지 의 경로 (4 연결) 가 존재 해 야 합 니 다. 만약 에 특정한 조작 이 요 구 를 만족 시 키 지 못 하면 하지 않 습 니 다. 마지막 에 몇 번 의 조작 이 성공 적 이 었 는 지 물 어보 세 요.
입력
첫 줄 세 개 r, c, n, 빈 칸 구분.
다음 n 줄, 줄 당 두 개의 x, y 는 삭제 할 칸 이 x 줄 y 열 에 있 음 을 표시 합 니 다.
출력
– 한 줄, 한 수 만 삭제 작업 의 수 를 표시 합 니 다.
샘플 입력
3 4 9 2 2 3 2 2 3 3 4 3 1 1 3 2 1 1 1 1 4
샘플 출력
6
제시 하 다.
30% 의 데이터, n < = 5000.
100% 의 데이터, r, c < = 3000, n < = 300000.
알고리즘

파 환 을 체인 으로 하여 그림 을 r * 2c

로 변경 합 니 다.

매번 칸 을 파 는 것 에 대해 그 를 주변 8 칸 안의 모든 칸 과 함께 통계

2 * 2c 를 덮어 쓰 는 사각형

이 있 는 지 확인 하고 집합 합 니 다.
코드

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define MAXN 3005
using namespace std;
int r,c,n,x,y,map[MAXN][MAXN<<1],fa[300005<<1],jud[300005<<1],cnt,ans;
int d[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
inline int find(int x)
{
    int father=x,ft=x,tmp;
    while(father!=fa[father])father=fa[father];
    while(ft!=father)
    {
        tmp=fa[ft];
        fa[ft]=father;
        ft=tmp;
    }
    return father;
}
inline bool judge(int x,int y)
{
    if(c==1)return 0;
    cnt++;
    for (int i=0;i<=1;i++)
    {
        if(i)y+=c;
        for (int j=0;j<8;j++)
        {
            int xt=x+d[j][0];
            int yt=y+d[j][1];
            if(yt<1)yt+=(c<<1);
            if(yt>(c<<1))yt-=(c<<1);
            if(map[xt][yt])
                if(!i)
                    jud[find(map[xt][yt])]=cnt;
                else
                    if(jud[find(map[xt][yt])]==cnt)return 0;
        }
    }
    return 1;
}
int main()
{
    scanf("%d%d%d",&r,&c,&n);
    for (int i=1;i<=n*2;i++)fa[i]=i;
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        if(judge(x,y))
        {
            map[x][y]=i;
            map[x][y+c]=i+n;
            for (int q=0;q<=1;q++)
            {
                if(q)y+=c;
                for (int j=0;j<8;j++)
                {
                    int xt=x+d[j][0];
                    int yt=y+d[j][1];
                    if(yt<1)yt+=(c<<1);
                    if(yt>(c<<1))yt-=(c<<1);
                    if(map[xt][yt])fa[find(map[x][y])]=find(map[xt][yt]);
                }
            }
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}