글 읽기 - 어떤경우가 안되는지 알고 싶습니다.

scared22 5년 전 0

제가 구현한 코드는 아래와 같습니다.

4차원 배열로 스위치를 킬 수 있는 정보를 저장했습니다.

2. 1,1부터 4차원 배열에 불을 킬수 있는 정보를 확인하여 불을 킬 수 있다면 result값을 증가시키고 불켜진 정보를 arr배열에 저장했습니다.

3. 상,하,좌,우로 탐색하면서 불이 켜진 곳으로 이동하여 1번부터 다시 반복작업을 합니다.

처음에 BFS 구현하여 아직 불이 켜지지도 않았는데 불이 켜질 수 있는 가능성이 있는 좌표를 arr에 저장하여 오답결과를 받아서 DPS로 변경하게 되었습니다.

어떤 경우를 제가 놓쳤는지 알고 싶습니다.

알려주세요 ㅜㅜ

#include <iostream>

using namespace std;

int possible[105][105][105][105], lighton[105][105], result, arr[105][105], visited[105][105];
int n, m;
void solve(int y, int x)
{
	if (y < 1 || y > n || x < 1 || x > n || visited[y][x] || !arr[y][x]) return;

	visited[y][x] = 1;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (possible[y][x][i][j] && !lighton[i][j])
			{
				result++;
				lighton[i][j]; // 한번 켰으면 두번키지 않도록 체크 
				arr[i][j] = 1; //스위치를 켰으면 길을 열어준다.
			}
		}
	}

	solve(y - 1, x);
	solve(y + 1, x);
	solve(y, x - 1);
	solve(y, x + 1);
}

int main()
{
	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		possible[a][b][c][d] = 1;
	}

	arr[1][1] = 1;
	lighton[1][1] = 1;
	solve(1,1);

	cout << result+1 << "\n";
	return 0;
}

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

문제

문제

출처

ICPC

어떤경우가 안되는지 알고 싶습니다.

scared22 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말