글 읽기 - 3145 지리지도 문제 어디가 틀린건지 잘 모르겠습니다.

victory277 6년 전 0

마을이름에 대해 각각 정점 번호를 매겨

'x'와 마을이름의 이분그래프에 대해 이분 매칭을 수행하여

매칭된 'x'의 좌표와 마을 이름을 출력하도록 했습니다.

예제는 잘 나오는데 어디를 어떻게 수정해야할지 잘 모르겠습니다.

도움 주시면 감사하겠습니다.

#include <iostream>
using namespace std;

typedef struct {
	int x, y;
}Point;

int N, M;
char map[50][50];
int dmap[50][50];
Point xp[1501];
char name[1000][50];
int index[1000];
int pc, np;
int d[1000][1000];

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

int n, m;
int aMatch[1000];
int bMatch[1000];
bool check[1000];

void getGraph() {
	int x, y;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 'x') {
				xp[++pc].x = j;
				xp[pc].y = i;
			}
			else if (map[i][j] != '.' && dmap[i][j] == 0) {
				x = j;
				y = i;

				np++;

				while (x < M && map[y][x] != 'x' && map[y][x] != '.') {
					dmap[y][x] = np;
					name[np][index[np]++] = map[y][x];

					x++;
				}
			}
		}
	}

	int tx, ty;

	n = pc;
	m = np;

	Point tmp;

	for (int i = 1; i < pc; i++) {
		for (int j = i + 1; j <= pc; j++) {
			if (xp[j].y < xp[i].y) {
				tmp = xp[i];
				xp[i] = xp[j];
				xp[j] = tmp;
			}
		}
	}

	for (int i = 1; i <= pc; i++) {
		x = xp[i].x;
		y = xp[i].y;

		for (int j = 0; j < 8; j++) {
			tx = x + dx[j];
			ty = y + dy[j];

			if (dmap[ty][tx] != 0) {
				d[i][dmap[ty][tx]] = 1;
			}
		}
	}
}

bool dfs(int a) {
	if (check[a]) return false;
	return true;

	for (int b = 1; b <= m; b++) {
		if (d[a][b]) {
			if (bMatch[b] == -1 || dfs(bMatch[b])) {
				bMatch[b] = a;
				aMatch[a] = b;
				return true;
			}
		}
	}
	return false;
}

void Matching() {
	for (int i = 1; i <= m; i++) {
		bMatch[i] = -1;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			check[j] = false;
		}

		dfs(i);
	}
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
		cin.ignore();
	}

	getGraph();
	Matching();

	for (int i = 1; i <= n; i++) {
		cout << xp[i].y + 1 << " " << xp[i].x + 1 << " ";

		int ind = -1;

		while (name[i][++ind] != NULL) {
			cout << name[i][ind];
		}

		cout << endl;
	}

	getchar();
	getchar();

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3145 지리지도 문제 어디가 틀린건지 잘 모르겠습니다.

victory277 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말