글 읽기 - 질문입니다.

jaewook5454 5년 전 0

거리 구할때 자기보다 큰 물고기는 못지나 가는 경우도 체크했고 테스트케이스도 잘 나오는데 어느 부분에서

틀렸는지 못찾겠습니다. 반례 찾아주시면 감사하겠습니다

#define _CRT_SECURE_NO_WARNINGS

#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int n, m, h;

int arr[20][20] = { 0, };
//int visited[20][20];
vector<pair<int, int>> fish[6];
int cmin;
int x, y;
int time;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int len(int x1, int y1,int x2, int y2,int size) {
	int tarr[20][20];
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {

			if (arr[i][j] > size&&arr[i][j]!=9) {
				tarr[i][j] = 1;
			}
			else
				tarr[i][j] = 0;
		}
	}

	queue<pair<int, int>> q;

	q.push({ x1,y1 }); 
	int visit[20][20];
	int cnt=0;
	while (q.size() != 0) {
		int qs = q.size();
		cnt++;
		while (qs--) {
			int cx = q.front().first;
			int cy = q.front().second;
			for (int i = 0;i < 4;i++) {
				int tx = cx + dx[i];
				int ty = cy + dy[i];
				if (tx < n&&tx >= 0 && ty  < n&&ty  >= 0&&tarr[tx][ty]==0)
				{
					if (visit[tx][ty] == 1)
						continue;
					if (tx == x2&&ty == y2) {
						return cnt;
					}
					q.push({ tx,ty });
					visit[tx][ty] = 1;
				}
			}
			q.pop();

		}

	}
	return -1;
}
int check(int x1,int y1,int size,int fishcnt) {

	int chkcnt=0;
	int t;
	if (size > 7)
		t = 7;
	else
		t = size;
	for (int i = 0;i < t-1;i++) {
		chkcnt += fish[i].size();
	}
	if (chkcnt == 0)
	{
		return time;
	}
	int cmin = 1000;
	int tmpj, fishsize;
	
	
	for (int i = 0;i < t-1;i++) {

		for (int j = 0;j < fish[i].size();j++) {
			int tmp = len(x1, y1, fish[i][j].first, fish[i][j].second,size);
			if (tmp == -1)
				continue;
			if (cmin > tmp) {
				cmin = tmp;
				tmpj = j;
				fishsize = i;
				
			}
			else if (cmin == tmp) {
				//fish[fishsize][tmpj] 현재 물고기 fish[i][j]
				if (fish[fishsize][tmpj].first > fish[i][j].first)//기존이 더 아래에 있으면
				{
					cmin = tmp;
					tmpj = j;
					fishsize = i;
				}
				else if (fish[fishsize][tmpj].first == fish[i][j].first&&fish[fishsize][tmpj].second > fish[i][j].second)//더 왼쪽이면
				{
					cmin = tmp;
					tmpj = j;
					fishsize = i;
				}
			}

		}
	}
	if (cmin == 1000)
		return time;
	time += cmin;
	x1 = fish[fishsize][tmpj].first;
	y1 = fish[fishsize][tmpj].second;
	//visited[x1][y1] = time;
	fish[fishsize].erase(fish[fishsize].begin() + tmpj);

	fishcnt++;

	if (fishcnt == size) {
		size++;

		check(x1, y1, size, 0);
	}
	else
		check(x1, y1, size, fishcnt);


}
int main() {




	scanf("%d", &n);
	
	for (int i = 0;i < n;i++) {

		for (int j = 0;j < n;j++) {

			scanf("%d", &arr[i][j]);
			if (arr[i][j] == 9) {
				x = i, y = j;
				continue;
			}
			if (arr[i][j] != 0) {
				fish[arr[i][j] - 1].push_back({ i,j });
			}
		}
	}

	time = 0;
	cout << check(x,y,2,0)<<endl;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++)
			cout << arr[i][j] << " ";
		cout << endl;
	}
	

	










}

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

문제

문제

출처

ICPC

질문입니다.

jaewook5454 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말