Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
3.2 kB
4
Indexable
Never

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <algorithm>

using namespace std;

int N, K, R;

bool vis[101][101];

struct ROAD{
    int r;
    int c;
    int r1;
    int c1;
    bool operator<(const ROAD& other) const {
        if (r != other.r) return r < other.r;
        if (c != other.c) return c < other.c;
        if (r1 != other.r1) return r1 < other.r1;
        return c1 < other.c1;
    }
};//ROADS[10000];

map<ROAD, bool> road_chk;


struct cow
{
    int r;
    int c;
    bool operator<(const cow& other) const {
        if (r != other.r) return r < other.r;
        return c < other.c;
    }

}COWS[10001];

map<cow,int> cow_nums;

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

bool inRange(int r, int c){
    return (0<=r && r<N && 0<=c && c<N);
}

int bfs(int r, int c){

    // 도로를 지나지 않는 곳에서부터 탐색 시작 
    // 그 이후에 들어가는 건 ok 
    memset(vis,false,sizeof(vis));

    queue<pair<int,int> > que;
    int cur_cnt = 0;
    vis[r][c] = true;

    for(int i = 0;i<4;i++){
        int nr = r + dy[i];
        int nc = c + dx[i];
        if(inRange(nr,nc)){
            if(!road_chk[ {r, c, nr, nc} ]){
                que.push({nr,nc});
                // cout << "next " << nr << " " << nc << '\n';
                vis[nr][nc] = true;
                if(cow_nums[{nr,nc}]>cow_nums[{r,c}]){
                    cur_cnt++;
                }
            }
        }
    }    

    // cout << "cow num " << cow_nums[{r,c}] << " que size "  << que.size() << '\n';
    while(!que.empty()){
        pair<int, int> cur_cow = que.front();
        int rr = cur_cow.first;
        int cc = cur_cow.second;
        que.pop();
        for(int i = 0;i<4;i++){
            int nr = rr + dy[i];
            int nc = cc + dx[i];
            if (inRange(nr,nc)) {
                if(!road_chk[{rr,cc,nr,nc}] && !vis[nr][nc]){
                    // 소가 아닐 때
                    que.push({nr,nc});
                    vis[nr][nc] = true;
                }
                else{ // 소일 때
                    if(cow_nums[{nr,nc}]>cow_nums[{r,c}] && !vis[nr][nc]){
                        vis[nr][nc] = true;
                        cur_cnt++;
                    }
                }
            }
        }
    }
    // cout << "cur_cnt " << cur_cnt << '\n';

    return cur_cnt;
}


int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> N >> K >> R;
    
    int r, c, r1, c1;
    for(int i = 0;i<R;i++){    
        // cin >> ROADS[i].r >> ROADS[i].c >> ROADS[i].r1 >> ROADS[i].c1;
        cin >> r >> c >> r1 >> c1;
        r--;
        c--;
        r1--;
        c1--;
        road_chk[{r,c,r1,c1}] = true;
        road_chk[{r1,c1,r,c}] = true;
    }

    int cow_cnt = 0;
    for(int i = 0;i<K;i++){
        cin >> COWS[i].r >> COWS[i].c;
        COWS[i].r--;
        COWS[i].c--;
    }
    
    sort(COWS, COWS+K);
    for(int i = 0 ;i<K;i++){
        cow_nums[COWS[i]] = ++cow_cnt;
        // cout << i << "th : " << COWS[i].r << " " << COWS[i].c << '\n';
    }


    int res = 0;
    for(int i = 0;i<K;i++){
        res += bfs(COWS[i].r, COWS[i].c);
    }

    cout << res << '\n';
    return 0;
}