글 읽기 - 이게 왜 틀렸을까요..

omh9876 2년 전 0

타잔알고리즘을 이용하여 2-SAT으로 풀었습니다.

위치추적기를 만날경우 가로,세로로 둘다 처리해주거나 둘다 처리해주지 않아야 하므로

ep(i, n + j);// i번째 줄 세로를 처리하는 경우는 i, j번째 줄 가로를 처리하는 경우는 n+j로 하고 f(i)는 !i를 반환
ep(f(i), f(n + j));//간선을 이어준다.
ep(n + j, i);
ep(f(n + j), f(i));

상황에 맞게 간선을 추가해주었고 위치추적기를 만났을 경우는

ep(i, f(n + j));
ep(f(i), n + j);
ep(n + j, f(i));
ep(f(n + j), i);

이렇게 간선을 추가해 주고 타잔알고리즘을 썼습니다.

구글링 해보니 저랑 거의 똑같이 푼 사람도 있던데 저는 14-16퍼에서 틀립니다.

아무리 생각해봐도 모르겠네요..

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct ee {
	int t;
	struct ee* next;
}ee;
typedef struct gg {
	ee* e;
}gg;

int n, m;
int ans = 0;
int dic[3005], id[3005], st[3005];
gg m2[3005];
int top = -1;
int nscc, nvtx;
int minn(int a, int b) { return a > b ? b : a; }

ee* cnode(int t) {
	ee* tn = (ee*)malloc(sizeof(ee));
	tn->t = t;
	tn->next = NULL; 
	return tn;
}
void ep(int s, int t) {
	ee* tn = cnode(t);
	if (m2[s].e == NULL) {
		m2[s].e = tn;

	}
	else {
		ee* ttn = m2[s].e;
		m2[s].e = tn;
		tn->next = ttn;
	}

}
int scc(int k) {
	int ret = dic[k] = nvtx++;
	st[++top] = k;
	ee* tn = m2[k].e;
	while (tn) {
		int t = tn->t;
		if (dic[t] == -1)ret = minn(ret, scc(t));
		else if (id[t] == -1)ret = minn(ret, dic[t]);

		tn = tn->next;
	}
	if (ret == dic[k]) {
		while (1) {
			int t = st[top--];
			id[t] = nscc;
			if (t == k)break;
			
		}
		nscc++;
	}
	return ret;

}
void targan() {
	nscc = 0, nvtx = 0; top = -1;
	memset(dic, -1, sizeof(dic));
	memset(id, -1, sizeof(id));
	for (int i = 0; i < 2*(n+m); i++) {
	//	printf("%d ", i);
		if (dic[i] == -1) {
			scc(i);
		}

	}
}
int f(int k) {
	int tn = n + m;
	return k >= tn ? k - tn : k + tn;
}

int main() {
	char tc;
	scanf(" %d %d", &n,&m);
	for (int i = 0; i <2*(n+m); i++) {//초기화
		m2[i].e = NULL;
	}
	for (int i = 0; i < n; i++) {//초기화
		for (int j = 0; j < m; j++) {
			scanf(" %c",&tc);
			if (tc == '.') {
				continue;
			}
			else if (tc == '*') {
				ep(i, f(n + j));//간선 넣기
				ep(f(i), n + j);
				ep(n + j, f(i));
				ep(f(n + j), i);
			}
			else if(tc=='#') {
				ep(i, n + j);
				ep(f(i), f(n + j));
				ep(n + j, i);
				ep(f(n + j), f(i));
			}			
		}
	}	
	targan();
	ans = 1;
	for (int i = 0; i <  n+m; i++) {
		if (id[i] == id[f(i)]) {
			ans = 0;
			break;
		}
	}	
	printf("%d\n",ans);

	

	return 0;
}

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

문제

문제

출처

ICPC

이게 왜 틀렸을까요..

omh9876 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말