글 읽기 - 반례를 찾고싶습니다

kdr06006 4년 전 0

맵의 좌표들을 1부터 숫자로 생각해서 정점으로 인식했습니다

H와 K가 붙어있으면 -1을 출력했고, 그게 아니면 인접리스트를 구현합니다.

방향을 아래, 오른쪽만 본 이유는 현재 좌표에서 왼쪽, 위쪽은 이 전 좌표에서 양방향 인접리스트를 구현할 때 아래, 오른쪽을 보면서 연결이 되므로 2방향만 봤습니다

질문게시판에 있는 반례들 다 넣어봤지만 반례를 못 찾았습니다

찾아주시면 감사하겠습니다

#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#define SIZE 10001
using namespace std;

int N, M, s, e, pre[SIZE];
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, value[] = { 123,1 };
char map[101][101];
queue<int>Q;

struct Edge {
	int to, c, f;
	Edge* reverse;

	Edge(int _to, int _c, int _f) {
		to = _to; c = _c; f = _f;
	}

	inline int spare() { return c - f; }
	inline void add(int F) {
		f += F;
		reverse->f -= F;
	}
};
vector<Edge*>adj[SIZE];
Edge* edge[SIZE];

int NF() {
	int ret = 0;
	while (1) {
		fill(pre + 1, pre + 1 + N * M, -1);
		fill(edge + 1, edge + 1 + N * M, nullptr);
		Q.push(s);
		while (!Q.empty() && pre[e] == -1) {
			int cur = Q.front(); Q.pop();
			for (auto a : adj[cur]) {
				int next = a->to;
				if (a->spare() > 0 && pre[next] == -1) {
					pre[next] = cur;
					Q.push(next);
					edge[next] = a;
				}
			}
		}

		while (!Q.empty()) Q.pop();

		if (pre[e] == -1) break;
		for (int i = e; i != s; i = pre[i]) {
			edge[i]->add(1);
			edge[i]->reverse->add(-1);
		}
		ret++;
	}
	return ret;
}

int main()
{
	scanf("%d %d", &N, &M);
	value[0] = M;;
	for (int i = 0; i < N; i++) {
		scanf("%s", map[i]);
	}

	int cur = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cur++;
			if (map[i][j] == '#') continue;
			else if (map[i][j] == 'K') s = cur;
			else if (map[i][j] == 'H') {
				e = cur;
				for (int k = 0; k < 4; k++) {
					int X = i + dx[k], Y = j + dy[k];
					if (X >= 0 && X < N && Y >= 0 && Y < M) {
						if (map[X][Y] == 'K') {
							printf("-1\n");
							return 0;
						}
					}
				}
			}

			for (int k = 0; k < 2; k++) {
				int X = i + dx[k], Y = j + dy[k];
				if (X >= 0 && X < N && Y >= 0 && Y < M) {
					if (map[X][Y] != '#') {
						Edge* edge1 = new Edge(cur + value[k], 1, 0);
						Edge* edge2 = new Edge(cur, 1, 0);
						edge1->reverse = edge2;
						edge2->reverse = edge1;
						adj[cur].push_back(edge1);
						adj[cur + value[k]].push_back(edge2);
					}
				}
			}
		}
	}

	printf("%d\n", NF());
}

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

문제

문제

출처

ICPC

반례를 찾고싶습니다

kdr06006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말