글 읽기 - 열심히 생각은 해봤는데 틀려서 반례가 궁금합니당 ㅠㅠ

gktgnjftm 5년 전 0

맨 처음에 1번 선수,2번선수,... 순서로 진행해야 되므로, 큐자료구조를 사용하였는데, 최대 si만큼 퍼질수 있기 때문에, 배열을 이용한 큐를 이용해 문제를 접근해서 풀어보았습니다.

확장을 하는데 있어서, 같은 팀을 만나거나, 벽을 만나거나, 다른팀을 만나거나, 범위를 벗어나면 더이상 확장하지 못하는 걸로 진행했습니다.

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <string>
#include <math.h>
#include <set>
#include <list>
#include <climits>
#include <string.h>
#include <deque>
#include <functional>
#include <stack>
using namespace std;
typedef long long ll;
#define mod 1000000009
#define lim 1000000000
typedef pair < int, int > P;
typedef pair<pair<int, int>, int> PP;
typedef pair<pair<int, int>, pair<int, int>> PPP;
int gox[4] = { 0,1,-1,0 };
int goy[4] = { 1,0,0,-1 };
char board[1001][1001];
int player[10];
map<int, int> mm;
int n, m, p;
void bfs() {
	bool visited[1001][1001] = { false, };
	queue<PP> q[10];
	for (int i = 1; i <= p; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= m; k++) {
				if (board[j][k] - '0' == i) {
					q[i].push({ { j,k },0 });
					visited[j][k] = true;
					mm[i]++;
				}
			}
		}
	}
	while (1) {
		int c = 0;
		for (int j = 1; j <= p; j++) {
			queue<PP> temp[10];
			if (q[j].empty()) c++;
			while (!q[j].empty()) {
				int x = q[j].front().first.first;
				int y = q[j].front().first.second;
				int ti = q[j].front().second;
				q[j].pop();
				if (ti == player[j]) { // 
					temp[j].push({ { x,y }, 0 });
					continue;
				}
				for (int i = 0; i < 4; i++) {
					for (int k = 1; k <= player[j]; k++) {
						int nx = x + k * gox[i];
						int ny = y + k * goy[i];
						if (nx<1 || nx>n || ny<1 || ny>m || board[nx][ny] == '#') break; // 범위를 벗어나거나 벽이거나 같은 성을 만나면 종료
						if (board[nx][ny] != '.' && board[x][y] != board[nx][ny]) break; // 다른 성을 만나면 종료
						if (!visited[nx][ny] && board[nx][ny] == '.' && ti + k <= player[j]) { // 만약 평지(.)이면 그 위치를 성으로 바꿔줌
							visited[nx][ny] = true;
							q[j].push({ { nx,ny }, ti + k });
							board[nx][ny] = j + '0';
							mm[j]++;
						}
					}
				}
			}
			q[j] = temp[j];
		}
		if (c == p) break; // 더이상 확장못함
	}
}
int main(void) {
	scanf("%d%d%d", &n, &m, &p);
	for (int i = 1; i <= p; i++) {
		scanf(" %d", &player[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &board[i][j]);
		}
	}
	bfs();

	map<int, int>::iterator it;
	int cnt = 0;
	for (it = mm.begin(); it != mm.end(); it++) {
		if (cnt == p-1) {
			printf("%d", it->second);
			continue;
		}
		printf("%d ", it->second);
		cnt++;
	}
	return 0;
}

lobo_prix 5년 전 1

반례입니다.

입력:

6 5 2
8 1
1....
.###.
..##.
#....
###.#
###2#

출력:

15 1

코드를 재밌게 짜두셔서 반례찾는데 꽤나 고생했네요.

힌트: queue에 집어넣는 순서

lobo_prix 5년 전 1

참고로 이 문제는 코드포스 div2 D번에 나왔던 문제라서 editorial이 있습니다. 참고하셔요

https://codeforces.com/blog/en...

gktgnjftm 5년 전 0

좋은 반례 감사합니다 ㅠㅠ, 고쳤는데 반례가 또 있는거같아용 ㅠㅠ, 참고하겠습니다 감사합니다

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

문제

문제

출처

ICPC

열심히 생각은 해봤는데 틀려서 반례가 궁금합니당 ㅠㅠ

gktgnjftm 5년 전 0

lobo_prix 5년 전 1

lobo_prix 5년 전 1

gktgnjftm 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말