글 읽기 - 어디를 고쳐야할까요오?

dhedaa 6년 전 0

비트마스트 + BFS 이용해서 정말 무난하게 짠거같은데

어디가 틀렸는지 모르겠습니당

그나마 문제가 있다면 visited 가 지나간곳인지 아닌지 보는 부분인거 같은데 조언좀 부탁드려요

다른분들은 visited를 지나갔나 체크하는 용도로 쓰신거 같은데 저는 가중치 1씩 더하면서 달을 찾았을 경우 최소값을 구했는데

이렇게 하면 안되나요?

//1194 달이 차오른다 가자

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <tuple>
using namespace std;
char map[51][51];
int visited[51][51][(1 << 6)];//x, y, key(a~f)
queue<tuple<int, int, int>> q;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < m; j++)
		{
			map[i][j] = str.at(j);
			if (map[i][j] == '0')
			{
				//민식이 위치 큐에 삽입
				visited[j][i][0] = 1;
				q.push(make_tuple(j, i, 0));
			}
		}
	}
	int res = 2147483647;
	while (!q.empty())
	{
		int x, y, z;
		tie(x, y, z) = q.front(); q.pop();
		if (map[y][x] == '1')
		{		
			if (visited[y][x][z] != 0 && res > visited[y][x][z])
				res = visited[y][x][z];			
		}
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];			
			if (nx > -1 && ny > -1 && nx < m && ny < n && map[ny][nx] != '#')
			{				
				//열쇠일 경우
				if (map[ny][nx] >= 'a' && map[ny][nx] <= 'z')
				{				
				    int nz = z | (1 << (map[ny][nx] - 'a'));
					if (visited[ny][nx][nz] == 0)
					{
						visited[ny][nx][nz] = visited[y][x][z] + 1;
						q.push(make_tuple(nx, ny, nz));
					}					
				}
				//문일 경우
				if (map[ny][nx] >= 'A' && map[ny][nx] <= 'Z'&& visited[ny][nx][z] == 0)
				{					
					if (z & (1 << (map[ny][nx] - 'A')))
					{						
						visited[ny][nx][z] = visited[y][x][z] + 1;
						q.push(make_tuple(nx, ny, z));
					}					
				}
				//그 외
				if(map[ny][nx] == '.' || map[ny][nx] == '0' || map[ny][nx] == '1')
				{
					if (visited[ny][nx][z] == 0)
					{
						visited[ny][nx][z] = visited[y][x][z] + 1;
						q.push(make_tuple(nx, ny, z));
					}					
				}				
			}
		}
	}
	if (res != 0)
		cout << res << endl;
	else
		cout << -1 << endl;
	return 0;
	
}

nohhans 6년 전 0

if (visited[ny][nx][nz] == 0)

이부분떄문에 한번움직인뒤부터는 열쇠를 먹을 수가 없을것 같네요

nohhans 6년 전 0

정확하게 지금 디버깅 해보진 않아서 잘모르겠지만

if (visited[ny][nx][nz] > visited[y][x][z] + 1) 이런식으로 들어가야 하지 않을까요?

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

문제

문제

출처

ICPC

어디를 고쳐야할까요오?

dhedaa 6년 전 0

nohhans 6년 전 0

nohhans 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말