소가 길을 건너간 이유 6 - 14466

//14466 - 소가 길을 건너간 이유 6
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, K, R;
int arr[100][100];
vector<vector<int>> adj;
bool isCow[10000];
int xarr[2] = {1, 0};
int yarr[2] = {0, 1};
vector<int> bucket;
bool visit[10000];
int count, ans;
 
int ch(int x1, int y1, int x2, int y2)
{
    if(y1 + 1 == y2) return 1;
    else if(x1 + 1 == x2) return 2;
    else return 0;
}
 
void init()
{
    cin >> N >> K >> R;
    ans = 0;
    bucket = vector<int>();
    adj = vector<vector<int>>(N*N);
    int x1, y1, x2, y2;
    for (int i = 0; i < R; ++i)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        --x1, --y1, --x2, --y2;
        if(x1 > x2 || y1 > y2) swap(x1, x2) , swap(y1, y2);
        arr[x1][y1] += ch(x1, y1, x2, y2);
    }
 
    for(int x = 0; x<N; ++x)
        for(int y = 0; y<N; ++y)
        {
            int here = x*N+y;
            int right = x*N+y+1;
            int down = (x+1)*N+y;
            if(y+1 == N) right = here;
            if(x+1 == N) down = here;
            if(!arr[x][y] || arr[x][y] == 1)
            {
                adj[here].push_back(down);
                adj[down].push_back(here);
            }
            if(!arr[x][y] || arr[x][y] == 2)
            {
                adj[here].push_back(right);
                adj[right].push_back(here);
            }
        }
    
    for(int i = 0; i<K; ++i)
    {
        cin >> x1 >> y1;
        --x1, --y1;
        isCow[x1*N+y1] = true;
    }
}
 
void dfs(int here)
{
    visit[here] = true;
    if(isCow[here]) ++count;
    for(int i = 0; i<adj[here].size(); ++i)
    {
        int there = adj[here][i];
        if(!visit[there])
            dfs(there);
    }
}
 
int main()
{
    init();
    for(int i = 0; i<N*N; ++i)
        if(!visit[i])
        {
            count = 0;
            dfs(i);
            bucket.push_back(count);
        }
 
    for(int i = 0; i<bucket.size(); ++i)
        for(int j = i+1; j<bucket.size(); ++j)
            ans += bucket[i]*bucket[j];
    cout << ans;
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/14466

14466번: 소가 길을 건너간 이유 6

 

 

 

 

 

 

소가 길을 건너간 이유 6

그래프로 모델링 한 후 dfs를 이용해 길을 건너지 않고 만날수 있는 소들의 마리수를 셌습니다.