글 읽기 - 어디가 문제일까요?(정답주의)

wogus23 3년 전 0

효율적이게 짜보겠다고 curRow,curCol이라는 시작 행열 위치를 매개변수로 두고 짜니까 틀리네요..

//틀린코드
void BackTracking(int**cost, int curRow, int curCol, int sum, int cnt,int n,bool**visit,int&ans)
{
    if (cnt == 3)
	{
		ans = std::min(sum, ans);
		return;
	}
	if (curCol >= n)//행 바꿈
	{
		curRow += 1;
		curCol = 1;
	}
	if (curRow >= n)
		return;
	int dx[5] = { 0,-1,1,0,0 };// 제자리 ,상,하,좌,우
	int dy[5] = { 0,0,0,-1,1 };
	for (int i = curRow; i < n - 1; i++)
	{
		for (int j = curCol; j < n - 1; j++)
		{
			bool det = true;
			for(int k=0;k<5;k++)
				if (visit[i+dx[k]][j+dy[k]])
				{
					det = false;
					break;
				}
			if (det)
			{
				int tmp = 0;
				for (int k = 0; k < 5; k++)
				{
					visit[i+dx[k]][j+dy[k]] = true;
					tmp+= cost[i+dx[k]][j+dy[k]];
				}
				BackTracking(cost,i,j+3, sum+tmp, cnt + 1, n, visit,ans);
				for (int k = 0; k < 5; k++)
					visit[i + dx[k]][j + dy[k]] = false;
				
			}
			
		}
	}
}

//정답코드
void BackTracking(int**cost,int sum, int cnt,int n,bool**visit,int&ans)
{
	int dx[5] = { 0,-1,1,0,0 };
	int dy[5] = { 0,0,0,-1,1 };
	if (cnt == 3)
	{
		ans = std::min(ans, sum);
		return;
	}
	for (int i = 1; i < n - 1; i++)
	{
		for (int j = 1; j < n - 1; j++)
		{
			bool det = true;
			for(int k=0;k<5;k++)
				if (visit[i + dx[k]][j + dy[k]])
				{
					det = false;
					break;
				}

			if (det)
			{
				int tmp = 0;
				for (int k = 0; k < 5; k++)
				{
					tmp += cost[i + dx[k]][j+dy[k]];
					visit[i + dx[k]][j + dy[k]]=true;
				}
				BackTracking(cost, sum + tmp, cnt + 1, n, visit, ans);
				for (int k = 0; k < 5; k++)
					visit[i + dx[k]][j + dy[k]]=false;

				
			}
		}
	}
}

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

문제

문제

출처

ICPC

어디가 문제일까요?(정답주의)

wogus23 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말