[위 키 오 이]1002 브리지(dfs+최소 생 성 트 리)

http://wikioi.com/problem/1002/
오늘부터 또 물 을 닦 기 시 작 했 습 니 다.하트T。hzwer 신 번 의 문제 풀이 기록 에 따라 솔!!!
문제 풀이:
처음 엔 나 도 못 했 는데 그냥 TT。
좋아,문제 풀이.
먼저 첫 번 째 질문 에 대해 우 리 는 직접 깊이 검색 하면 됩 니 다.연 결 된 도 시 를 따라 가면 됩 니 다.처음 엔 몰 랐 는데!!)
그러면 우 리 는 이 도시 들 을 축소 점 후의 점 집 x 로 볼 수 있다.
그 다음 에 우 리 는 다시 검색 해서 각'\#'점 에서 출발 하여 네 방향 으로 확대 한다(정확히 말 하면 네 방향 이 고 각 방향 은 3 줄(열)!).점 집 x 의 서로 다른 점 을 연결 시 키 고 여기에 가지치기 가 있 습 니 다.만약 에 특정한 방향 을 넓 힐 때 자신 이 점 집 과 같은 점 을 만 났 을 때 확장 을 중단 할 수 있 습 니 다.이 유 는 너무 간단 해서 스스로 생각한다.
그리고 끝 을 이 어 최소 생 성 트 리 로 달 려 갑 니 다.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getnum()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

inline int getnum() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=60;

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

struct ED { int x, y, w; }e[N*N*N];

int n, m, a[N][N], d[N][N], ans, sum, cnt, p[N*N];

inline const bool cmp(const ED &a, const ED &b) { return a.w<b.w; }

const int ifind(const int &x) { return x==p[x]?x:p[x]=ifind(p[x]); }



void dfs1(const int &x, const int &y) {

	int fx, fy;

	d[x][y]=ans;

	rep(i, 8) {

		fx=x+dx[i]; fy=y+dy[i];

		if(fx<1 || fx>n || fy<1 || fy>m || d[fx][fy] || !a[fx][fy]) continue;

		dfs1(fx, fy);

	}

}

void work1() {

	for1(i, 1, n) for1(j, 1, m) if(a[i][j] && !d[i][j]) { ++ans; dfs1(i, j); }

	printf("%d
", ans);

}

inline const bool insert(const int &fx, const int &fy, const int &x, const int &y, const int &w) {

	if(x<1 || x>n || y<1 || y>m || !d[x][y]) return 1;

	if(d[x][y]==d[fx][fy]) return 0;

	e[++cnt].x=d[fx][fy]; e[cnt].y=d[x][y];

	e[cnt].w=w-1;

	return 1;

}

void build(const int &x, const int &y) {

	for1(i, x+1, n) if(!insert(x, y, i, y, i-x) || !insert(x, y, i, y+1, i-x) || !insert(x, y, i, y-1, i-x)) break;

	for3(i, x-1, 1) if(!insert(x, y, i, y, x-i) || !insert(x, y, i, y+1, x-i) || !insert(x, y, i, y-1, x-i)) break;

	for1(i, y+1, m) if(!insert(x, y, x, i, i-y) || !insert(x, y, x+1, i, i-y) || !insert(x, y, x-1, i, i-y)) break;

	for3(i, y-1, 1) if(!insert(x, y, x, i, y-i) || !insert(x, y, x+1, i, y-i) || !insert(x, y, x-1, i, y-i)) break;

}

void work2() {

	for1(i, 1, n) for1(j, 1, m) if(a[i][j]) build(i, j);

	sort(e+1, e+1+cnt, cmp);

	for1(i, 1, ans) p[i]=i;

	sum=ans=0; int fx, fy;

	for1(i, 1, cnt) {

		fx=ifind(e[i].x); fy=ifind(e[i].y);

		if(fx!=fy) {

			p[fx]=fy;

			++ans;

			sum+=e[i].w;

		}

	}

	printf("%d %d
", ans, sum);

}



int main() {

	read(n); read(m); char c;

	for1(i, 1, n) for1(j, 1, m) {

		for(c=getchar(); c!='#'&&c!='.'; c=getchar());

		if(c=='#') a[i][j]=1;

	}

	work1();

	work2();

	return 0;

}

 
 
 
 
제목 설명
사각형 구역 이 있 는 도시 에서 몇 개의 건축물 을 지 었 는데 만약 에 두 개의 단원 격 이 하나의 점 과 연결 되 어 있다 면 그들 은 같은 건축물 에 속한다.지금 은 이 건물 들 사이 에 다 리 를 놓 으 려 고 하 는데 그 중에서 다 리 는 사각형 의 사각형 가장자리 에 만 세 워 질 수 있다.예 를 들 어 아래 도시 에 5 개의 건축물 이 있 으 면 4 개의 다 리 를 만들어 건물 을 연결 시 킬 수 있다.도시 2 에는 두 개의 건물 이 있 지만 다 리 를 만들어 연결 할 수 는 없다.도시 3 에는 건물 이 하나 뿐 이 고 도시 4 에는 3 개의 건물 이 있어 다 리 를 놓 아 두 건물 을 연결 할 수 있 지만 세 번 째 건물 과 는 연결 되 지 않 는 다.
입력 설명 입력 설명
입력 한 데이터 의 첫 번 째 줄 은 도 시 를 묘사 하 는 두 개의 정수 r 와 c 를 포함 하고 각각 북 에서 남,동 에서 서 까지 의 도시 크기(1<== r <= 50 and 1 <=  c<=50).다음 r 줄,줄 마다 c 개("\#")와(".")로 구 성 된 문자 입 니 다.문자 마다 셀 을 표시 합 니 다."\#"공 터
 
출력 설명 출력 설명
출력 된 데이터 에는 두 줄 이 있 고 첫 줄 은 건축물 의 수 를 나타 낸다.두 번 째 줄 의 수출 다리 의 수량 과 모든 다리 의 총 길이.
샘플 입력 샘플 입력
샘플 1
3 5
#...#
..#..
#...#
 
샘플 2
3 5
##...
.....
....#
 
본보기
3 5
#.###
#.#.#
###.#
 
예시 4:
3 5
#.#..
.....
....#
 
샘플 출력 샘플 출력
샘플 1
5
4 4
 
샘플 2
2
0 0
 
본보기
1
0 0
 
본보기
3
1 1
데이터 범위 및 알림 Data Size&Hint
설명 을 보다