글 읽기 - 코드 계속 봤는데, 문제 없어 보이는데 예제 몇 개는 맞고, 몇 개는 틀리네요ㅜㅜ

alsrjs2516 2년 전 0

살아있는 물고기 정보 벡터 vector<pair<pair<int,int>, pair<int,int>> fInfo 넘겨주면서 dfs 타는 식으로 구현했습니다.

(숫자 번호, 방향, 위치 x, y)

맵에 살아있는 물고기 정보 표현하고

물고기 이동하고

상어가 물고기 있는 곳으로 갈 수 있으면

새로 벡터 하나만들어서 그 물고기 죽이고 dfs 또 타는 식이에요

흐음 문제없는 것 같은데ㅜㅜ 왜 그럴까요? 도와주세요오!~~!~~~~

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,-1,-1,-1,0,1,1,1 };
int maxSum = 0;

//할 때 마다 맵 정보, 물고기 정보가 너무 많이 변해서 들고 다니자..
void dfs(int sx, int sy, int sdir, int sum, vector<pair<pair<int, int>, pair<int, int>>> fInfo) {
	int fil = fInfo.size();
	maxSum = max(maxSum, sum);

	int map[5][5] = { 0, };
	int cache[20] = { 0, };
	map[sx][sy] = -1;
	for (int i = 0; i < fil; i++) {
		//물고기 정보들 맵에 표현하고
		map[fInfo[i].second.first][fInfo[i].second.second] = fInfo[i].first.first;
		//물고기 번호와 fInfo 인덱스 사이의 관계도 저장해놓자
		cache[fInfo[i].first.first] = i;
	}

	//물고기 이동하고
	for (int i = 0; i < fil; i++) {
		//현재 보고있는 물고기 정보
		int fnum = fInfo[i].first.first;
		int fdir = fInfo[i].first.second;
		int fx = fInfo[i].second.first;
		int fy = fInfo[i].second.second;

		//8방향 보면서 가능한 쪽으로 이동
		for (int j = 0; j < 8; j++) {
			int nfdir = (fdir + j) % 8;
			int nfx = fx + dx[nfdir];
			int nfy = fy + dy[nfdir];
			if (nfx < 0 || nfy < 0 || nfx >= 4 || nfy >= 4) continue;

			int nfnum = map[nfx][nfy];
			if (map[nfx][nfy] == -1) continue;

			int ni = cache[nfnum];

			//이 방향으로 이동 가능하면 정보업데이트
			fInfo[i].first.second = nfdir;
			fInfo[i].second.first = nfx;
			fInfo[i].second.second = nfy;

			fInfo[ni].second.first = fx;
			fInfo[ni].second.second = fy;

			map[nfx][nfy] = fnum;
			map[fx][fy] = nfnum;
			break;
		}
	}

	//상어가 갈 수 있는 방향으로 추추추 타고 들어가면서
	int nsx = sx;
	int nsy = sy;
	while (true) {
		nsx += dx[sdir];
		nsy += dy[sdir];

		if (nsx < 0 || nsy < 0 || nsx >= 4 || nsy >= 4) {
			break;
		}

		int fnum = map[nsx][nsy];
		//물고기 먹을 수 있으면 dfs!
		if (fnum != 0) {
			int fi = cache[fnum];
			int fdir = fInfo[fi].first.second; //상어가 물고기 방향으로 바뀜
			vector<pair<pair<int, int>, pair<int, int>>> newFInfo = fInfo;
			newFInfo.erase(newFInfo.begin() + fi);

			dfs(nsx, nsy, fdir, sum + fnum, newFInfo);
		}
	}
}

int main() {
	int firstSum = 0;
	int firstDir = 0;
	//번호, 방향, 위치
	vector<pair<pair<int, int>, pair<int, int>>> firstFishInfo;

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int a, b;
			cin >> a >> b;
			if (i == 0 && j == 0) {
				firstSum += a;
				firstDir = b - 1;
			}
			else {
				firstFishInfo.push_back({ {a, b - 1},  {i, j} });
			}

		}
	}

	//번호가 작은 순으로 이동할거니까!
	sort(firstFishInfo.begin(), firstFishInfo.end());

	dfs(0, 0, firstDir, firstSum, firstFishInfo);

	cout << maxSum;

	return 0;
}

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

문제

문제

출처

ICPC

코드 계속 봤는데, 문제 없어 보이는데 예제 몇 개는 맞고, 몇 개는 틀리네요ㅜㅜ

alsrjs2516 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말