글 읽기 - 91% 탈락.... 반례 부탁드립니다.

kzeroc0 1년 전 0

비활성 바이러스 시간도 고려해서

질문게시판에있는 모든 testcase 통과하였으나,, 91%에서 탈락입니다.

고수분들께서 도와주시면 감사하겠숩니다 ㅜ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

int N, M;
int tempret = 10000000, ret = 10000000;
int map[50][50];
int cop[50][50];
bool visit[50][50];

struct coord {
	int y, x, c;
};
vector<coord> v;
vector<coord> selv;
queue<int> qy, qx, qc, qd;

bool judge(int y, int x)
{
	int upy = y - 1; int upx = x;
	int downy = y + 1; int downx = x;
	int righty = y; int rightx = x - 1;
	int lefty = y; int leftx = x + 1;
	if (upy >= 0 && upy <= N - 1 && upx >= 0 && upx <= N - 1) {
		if (cop[upy][upx] == 0) {
			return true;
		}
	}//상
	if (downy >= 0 && downy <= N - 1 && downx >= 0 && downx <= N - 1) {
		if (cop[downy][downx] == 0) {
			return true;
		}
	}//하
	if (righty >= 0 && righty <= N - 1 && rightx >= 0 && rightx <= N - 1) {
		if (cop[righty][rightx] == 0) {
			return true;
		}
	}//우
	if (lefty >= 0 && lefty <= N - 1 && leftx >= 0 && leftx <= N - 1) {
		if (cop[lefty][leftx] == 0) {
			return true;
		}
	}//좌
	return false;
}


bool conti(int y, int x, int c, int by, int bx)
{
	if (y < 0 || y >= N || x < 0 || x >= N) {
		return false;
	}
	else if (visit[y][x] == true) {
		return false;
	}
	else if (cop[y][x] == 1 || cop[y][x] == 2) {
		return false;
	}
	if (cop[y][x] == 3 && !judge(y,x)) {
		qc.push(c); qd.push(c);
	}
	else {
		qc.push(c + 1); qd.push(c + 1);
	}
	visit[y][x] = true;
	cop[y][x] = 2;
	return true;
}

void bfs()
{
	int cnt = 0;
	for (int i = 0; i < selv.size(); i++) {
		qy.push(selv[i].y), qx.push(selv[i].x), qc.push(selv[i].c);
		visit[selv[i].y][selv[i].x] = true;
		cop[selv[i].y][selv[i].x] = 2;
	}

	while (!qy.empty()) {
		int ny = qy.front();
		int nx = qx.front();
		int nc = qc.front();
		qy.pop(), qx.pop(), qc.pop();

		if (conti(ny - 1, nx, nc, ny, nx)) { 			//상
			qy.push(ny - 1), qx.push(nx);
		}
		if (conti(ny + 1, nx, nc, ny, nx)) {			//하
			qy.push(ny + 1), qx.push(nx);
		}
		if (conti(ny, nx - 1, nc, ny, nx)) {			//좌
			qy.push(ny), qx.push(nx - 1);
		}
		if (conti(ny, nx + 1, nc, ny, nx)) {			//우
			qy.push(ny), qx.push(nx + 1);
		}
	}
	while (!qd.empty()) {
		int temp = qd.front();
		qd.pop();
		cnt = max(temp, cnt);
	}
	int tempsw = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (cop[i][j] == 0) {
				tempsw = 1;
			}
		}
	}
	if (tempsw == 1) {
		cnt = 100000;
	}
	tempret = min(tempret, cnt);
	memset(visit, false, sizeof(visit));
}

void select(int cnt)
{

	if (selv.size() == M) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cop[i][j] = map[i][j];
			}
		}
		bfs();
		ret = min(tempret, ret);
		return;
	}

	for (int i = cnt; i < v.size(); i++) {
		selv.push_back(v[i]);
		select(i + 1);
		selv.pop_back();
	}
}

int main(void)
{
	coord c;
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 2) {
				map[i][j] = 3;
				c.y = i, c.x = j; c.c = 0;
				v.push_back(c);
			}
		}
	}
	select(0);
	if (ret == 100000) {
		printf("%d\n", -1);
	}
	else {
		printf("%d\n", ret);
	}
	return 0;
}

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

문제

문제

출처

ICPC

91% 탈락.... 반례 부탁드립니다.

kzeroc0 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말