글 읽기 - 반례도 다맞는데 30%에서 틀립니다.

karlema 4년 전 0

반례나 고칠좀 있으면 알려주시면 감사할게요...

// 30%에서 틀렸습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
int map[51][51]; // 맵을 갱신한다.
int tempmap[51][51]; //템프맵을 보고
int visit[51][51];
int back[51][51];
vector<pair<int, int>>v;
int vectorsize[3000];
int result = 987654321;
queue <pair<int, int>>q;
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int cnt;
int total;
int virus;
void init()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			tempmap[i][j] = map[i][j];
			visit[i][j] = 0;
			virus = 0;
		}
	}
}
void backprint()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			printf("%d ", back[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
void print()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			printf("%d ", tempmap[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
void vectprint()
{
	for (int i = 0; i < v.size(); i++)
	{
		printf("%d ", vectorsize[i]);
	}
	printf("\n");
}
void printvisit()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			printf("%d ", visit[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
void bfs()
{
	//printf("\nstart : ");
	cnt = 0;
	
	while (!q.empty())
	{
		
		int qsize = q.size();
		int cy = q.front().first;
		int cx = q.front().second;
		//printf("%d %d\n",cy,cx);
		visit[cy][cx] = 1;
		//printf("bfs start %d %d\n", virus, total);
		
		//printf("%d\n",cnt);
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (ny < 0 || nx < 0 || ny >= n || nx >= n || visit[ny][nx] == 1 || tempmap[ny][nx] == 45) continue;
			q.push(make_pair(ny, nx));
			//printf("%d %d\n", virus, total);
			if (tempmap[ny][nx] == 0) virus++;
			visit[ny][nx] = 1;
			tempmap[ny][nx] = tempmap[cy][cx] + 1;
			cnt = tempmap[ny][nx];
		}

		//printf("%d", cnt);
		if (virus == total)
		{
			if (result > cnt) result = cnt;
			//printf("결과 : %d\n", result);
			break;
		}
	}
	
	
	return;
}
void dfs(int cnt, int y, int x)
{
	if (cnt >= m)
	{
		//vectprint();
		//print();
		//result++;
		while (!q.empty()) q.pop();
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (back[i][j] == 1)
				{
					//printf("bfs start %d %d\n", i, j);
					q.push(make_pair(i, j));
					tempmap[i][j] = 0;
					
				}
				if (tempmap[i][j] == 2)	tempmap[i][j] = '*';
				if (tempmap[i][j] == 1) tempmap[i][j] = '-';
			}
		}
		//print();
		bfs();
		//printf("\n");
		//backprint();
		//print();
		//printvisit();
		//printf("%d\n",result);
		init();
		return;
	}

	for (int i = y; i < n; i++)
	{
		for (int j = x; j < n; j++)
		{
			if (tempmap[i][j] == 2 && back[i][j] == 0)
			{
				back[i][j] = 1;
				dfs(cnt + 1, i, j);
				back[i][j] = 0;
			}
		}
		x = 0;
	}
	return;
}
int main()
{
	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)
			{
				v.push_back(make_pair(i, j));
			}
			if (map[i][j] == 0)	total++;
		}
	};
	if (0 == total)
	{
		printf("0");
		return 0;
	}
	init();
	dfs(0, 0, 0);
	if (result == 987654321) result = -1;
	printf("%d", result);
	return 0;
}

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

문제

문제

출처

ICPC

반례도 다맞는데 30%에서 틀립니다.

karlema 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말