글 읽기 - 다른건 맞는데 예제 1개에서 무한루프에 들어갑니다...

culture1123 5년 전 0

다른 예제는 잘 돌아가는데

예제 4번에서만 무한루프 들어가네요....

풀이는

bfs로 최소 찾은다음

정답 찾고 초기화 순으로 했습니다..

고수분들 도와주세요...

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

int n;
int map[21][21];
int visit[21][21];
int sr, sc;
int dc[4] = { 0,-1,1,0 };
int dr[4] = { -1,0,0,1 };
int r, c;
int nr, nc;
int ans = 0;
/*
void mapshow()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}

void visitshow()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << visit[i][j] << " ";
		}
		cout << endl;
	}
}
*/
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int x;
			cin >> x;
			map[i][j] = x;
			if (map[i][j] == 9)
			{
				sr = i;
				sc = j;
			}
		}
	}
	
	int flag = 1;
	int shark_mom = 1;
	int shark_size = 2;
	int cnt = 0;
	int num = 0;
	int eat_flag = 0;
	int fi, fj;
	int size_flag = 0;
	while (flag)
	{
		memset(visit, 0, sizeof(visit));
		shark_mom = 1;
		
		//종료조건 검사
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (map[i][j] >0 && map[i][j] < shark_size)
				{
					shark_mom = 0;
				}
				
				if (shark_mom == 0)
				{
					break;
				}
			}
			if (shark_mom == 0)
			{
				break;
			}
		}

		if (shark_mom == 1)
		{
			cout << ans << endl;
			break;
		}


		queue<pair<int, int>> q;
		q.push(make_pair(sr, sc));
		visit[sr][sc] = 1;
		eat_flag = 0;
		size_flag = 0;
		while (!q.empty())
		{
			r = q.front().first;
			c = q.front().second;
			q.pop();
			
			for (int i = 0; i < 4; i++)
			{
				nr = r + dr[i];
				nc = c + dc[i];
				if (nr < 0 || nc < 0 || nr >= n || nc >= n)
					continue;

				if (visit[nr][nc] == 0)
				{
					if (map[nr][nc] == 0)
					{
						//cout << "nr" << nr << "nc" << nc << endl;
						//cout << "pass" << endl;
						q.push(make_pair(nr, nc));
						visit[nr][nc] = visit[r][c]+1;
					}
					else if (map[nr][nc] == shark_size)
					{
						//cout << "nr" << nr << "nc" << nc << endl;
						//cout << "same" << endl;
						q.push(make_pair(nr, nc));
						visit[nr][nc] = visit[r][c]+1;
					}
					else if (map[nr][nc] > shark_size)
					{
						//cout << "nr" << nr << "nc" << nc << endl;
						//cout << "truepass" << endl;
						size_flag = 1;
						continue;
					}
					else if (map[nr][nc] < shark_size)
					{
						//mapshow();
						num++;
						visit[nr][nc] = visit[r][c] + 1;
						map[nr][nc] = shark_size;
						map[sr][sc] = 0;
						sr = nr;
						sc = nc;
						eat_flag = 1;
						fi = nr;
						fj = nc;
						
						ans = ans + visit[nr][nc] - 1;
				//		cout << "shark-size" << shark_size << endl;
				////		cout << "visit[nr][nc]"<< visit[nr][nc] - 1 << endl;
				//		cout << "ans" << ans<<endl;
				//		mapshow();
						//visitshow();
				//		cout << endl;
						if (num == shark_size)
						{
							shark_size++;
							num = 0;
						}
						if (eat_flag == 1)
						{
							break;
						}
					}
				}
			}
			if (eat_flag == 1)
			{
				break;
			}
			if (size_flag == 1)
			{
				continue;
			}
		

			
		}


		
	}
	return 0;
}

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

문제

문제

출처

ICPC

다른건 맞는데 예제 1개에서 무한루프에 들어갑니다...

culture1123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말