글 읽기 - 도움 부탁드립니다..

crypt9 3년 전 0

다른 방법으로 풀긴 했습니다만,

아래와 같이 코딩을 하면 50%에서 틀렸다고 하는데 아무리 확인 해봐도 이해가 안되서 도움 요청 드립니다.

가로문자들의 배열 hmap[2000][2000] 과 세로문자들의 배열 vmap[2000][2000] 에 입력 문자들을 저장하고,

두 배열이 다른 값을 가지는 위치를 찾아서 (i --> j) 간선을 생성하고 2000개 행 기준으로 이분매칭을 진행하였습니다.

어느 부분이 문제일까요?

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <unordered_map>
using namespace std;

const int LEN = 2002;
int A[LEN], B[LEN];
bool visit[LEN];
vector<int> adj[LEN];
char hmap[LEN][LEN], vmap[LEN][LEN];
int T,H,V;


int dfs(int a)
{
	if( visit[a] ) return false;
	visit[a] = true;
	
	for(int b : adj[a]) {
		if( B[b]==-1 || dfs(B[b]) ) {
			B[b] = a;
			A[a] = b;
			return true;
		}
	}

	return false;
}

int main()
{
	scanf(" %d", &T);
	while( T-- ) {
		
		// 초기화  
		memset(A, -1, sizeof(A));
		memset(B, -1, sizeof(B));
		memset(hmap, 0, sizeof(hmap));
		memset(vmap, 0, sizeof(vmap));
		for(int i=0; i<LEN; i++) adj[i].clear();

		scanf(" %d %d", &H, &V);
		int x,y,len;
		char s[LEN]; 
		
		// 가로 문자들 저장 
		for(int i=0; i<H; i++) {
			scanf(" %d %d %s", &x,&y,s);
			len = strlen(s);
			for(int j=0; j<len; j++) {
				hmap[y][x+j] = s[j];
			}
		}
		
		// 세로 문자들 저장  
		for(int j=0; j<V; j++) {
			scanf(" %d %d %s", &x,&y,s);
			len = strlen(s);
			for(int i=0; i<len; i++) {
				vmap[y+i][x] = s[i];
			}
		}
		
		// 충돌난 위치를 찾아 간선을 생성  
		for(int i=0; i<LEN; i++) {
			for(int j=0; j<LEN; j++) {
				if( hmap[i][j] && vmap[i][j] && hmap[i][j] != vmap[i][j] ) {
					adj[i].push_back(j);
				}
			}
		}
		
		// 이분매칭  (2000 행 전체) 
		int cnt=0;
		for(int a=0; a<LEN; a++) {
			if( A[a]==-1 ) {
				fill(visit, visit+LEN, false);
				if( dfs(a) ) cnt++;
			}
		}
		
		printf("%d\n", H+V-cnt);
	}
	
	return 0;
}

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

문제

문제

출처

ICPC

도움 부탁드립니다..

crypt9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말