글 읽기 - 17142 반례좀 찾아주세요 (c++)!!!

gh5736 3년 전 0

13%에서 항상 틀립니다......ㅠㅠ

고수님들

부탁드립니다.

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<iostream>
#include<queue>
#include<algorithm>

#include<string.h>
//memset!!!


#define max  51
#define maxval  987654321

using namespace std;

int N, M = 0;
int mcount = 0;
int check = 0;
int time = 0;

int result = maxval;
int mintime = 987654321;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { -1, 1, 0, 0 };

int m[max][max] = { 0, };
int c[max][max] = { 0, };//몇번만에 퍼지는지 확인

queue<pair<int, int>> q;

void bfs()
{
#if 1

	memset(c, 0, sizeof(c)); //string.h
	//int c[max][max] = { 0, };
	check = 0;
	//ok

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		//printf("바이러스 %d,%d\n", x, y);// 바이러스 좌표 획득

		q.pop();

		for (int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (0 <= nx && 0 <= ny&& nx < N &&  ny < N) //!!  등호
			{
				//1.벽은 지나갈수 없다. 1 = 벽
				//2.활성이 비활성 만나면 활성화됨
				if (m[nx][ny] != 1 && c[nx][ny] == 0 )
				{

					c[nx][ny] = c[x][y] + 1; // check and 퍼짐 cnt
					
					if (m[nx][ny] == 0){
						check++; //맵 다 돌았는지 확인용
						time = c[nx][ny]; //맵 걸린시간 확인용
					}
					
					q.push(make_pair(nx, ny));
					
				}
			}
		}
		
	}
	//printf("check %d  %d\n", mcount,time);
	if (check == mcount)
	{
		mintime = min(mintime, time);
		result = mintime;

	}
	////몇개는 바이러스가 다 퍼지고, 
	//몇개는 다 바이러스가 아퍼질때
	// result가 min을 한번도 찾지못하고 처음 선언했던 max 값일때 -1 출력
	if (result == maxval)
	{
		result = -1;
	}

	//printf("bfs끝 \n");
#endif 
}

int main()
{
	vector<pair<int, int>> v;
	vector<int> idx;
	
    scanf("%d %d", &N, &M);

	for (int i = 0; i < N;i++){
		for (int j = 0; j < N; j++){
			scanf("%d", &m[i][j]);//&m[][]

			if (m[i][j] == 2)
			{
				v.push_back(make_pair(i, j));
			}
			if (m[i][j] == 0)
				mcount += 1;
		}
	}

	for (int i = 0; i < M; i++)
		idx.push_back(1);
	
	int vs = v.size();
	for (int i = 0; i < vs-M; i++)
		idx.push_back(0);
	
	sort(idx.begin(), idx.end());

	do
	{
		//vector<pair<int, int>> s;
		int vs = v.size();
		for (int i = 0; i < vs; i++){
			if (idx[i] == 1){
				q.push(make_pair(v[i].first, v[i].second));
			}
		}
		bfs();
		
	} while (next_permutation(idx.begin(), idx.end()));// ;!!!
	


	printf("%d",result);
	return 0;
} 

gh5736 3년 전 0

찾았습니다!!

kimmykim_jy 2년 전 0

저도 예시는 다 맞는데 13% 쯤에서 계속 틀리는데 혹시 반례가 뭘까요 ㅠㅠ?

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

문제

문제

출처

ICPC

17142 반례좀 찾아주세요 (c++)!!!

gh5736 3년 전 0

gh5736 3년 전 0

kimmykim_jy 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말