글 읽기 - BFS상태그래프로 구현했는데 틀렸습니다 도와주세요 ㅜㅜ

isvara 4년 전 0

BFS상태그래프로 풀어보았는데 틀리는군요 ㅜ..

왠만한 게시판에 예제다넣어봤는데 잘돌아가는것같습니다.

혹시 어디가 잘못됬는지 지적이나 반례가 있을까요???

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<string.h>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;

int N;
vector<vector<int>>board;
void move(vector<vector<int>> &m, int dir) { //상하좌우로 움직이는 코드
 	if (dir == 0) {//위
		for (int col = 0; col <N; col++){
			vector<int>trim;//공백제거 배열
			vector<int>result;//결과 배열
			for (int row = 0; row < N; row++)
			{
				if (m[row][col] != 0)
					trim.push_back(m[row][col]);
			}
			for (int k = 0; k < trim.size(); k++) {
				if (k + 1 < trim.size() && trim[k] == trim[k + 1])
				{
					result.push_back(trim[k] * 2);
					k++;
				}
				else
					result.push_back(trim[k]);
			} 
			for (int i = 0; i < N; i++)
			{
				if (i < result.size())
					m[i][col] = result[i];
				else
					m[i][col] = 0;
			}
		}
	}
	else if (dir == 1) {//오른쪽
		for (int row = 0; row < N; row++) {
			vector<int>trim;
			vector<int>result;
			for (int col = N-1; col >0; col--)
			{
				if (m[row][col] != 0)
					trim.push_back(m[row][col]);
			}
			for (int k=0; k <trim.size(); k++) {
				if (k + 1 <trim.size() && trim[k] == trim[k + 1])
				{
					result.push_back(trim[k] * 2);
					k++;
				}
				else
					result.push_back(trim[k]);
			}
			for (int i = 0; i < N; i++)
			{
				if (i < result.size())
					m[row][N-i-1] = result[i];
				else
					m[row][N-i-1] = 0;
			}
		}
	}
	else if (dir == 2) {//아랫쪽
		for (int col = 0; col < N; col++) {
			vector<int>trim;
			vector<int>result;

			for (int row = N - 1; row >= 0; row--)
			{
				if (m[row][col] != 0)
					trim.push_back(m[row][col]);
			}
			for (int k =0; k <trim.size(); k++) {
				if (k + 1 < trim.size() && trim[k] == trim[k + 1])
				{
					result.push_back(trim[k] * 2);
					k++;
				}
				else
					result.push_back(trim[k]);
			}
			for (int i = 0; i < N; i++) {
				if (i < result.size())
					m[N - i - 1][col] = result[i];
				else
					m[N - i - 1][col] = 0;
			}
		}
	}
	else if (dir == 3) {//왼쪽
	for (int row = 0; row < N; row++) {
		vector<int>trim;
		vector<int>result;

		for (int col = 0; col<N; col++)
		{
			if (m[row][col] != 0)
				trim.push_back(m[row][col]);
		}
		for (int k = 0; k < trim.size(); k++) {
			if (k + 1 < trim.size() && trim[k] == trim[k + 1])
			{
				result.push_back(trim[k] * 2);
				k++;
			}
			else
				result.push_back(trim[k]);
		}
		for (int i = 0; i < N; i++) {
			if (i < result.size())
				m[row][i] = result[i];
			else
				m[row][i] = 0;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		vector<int>v;
		for (int j = 0; j < N; j++)
		{
			int tmp;
			cin >> tmp;
			v.push_back(tmp);
		}
		board.push_back(v);
	}
	queue < pair<vector<vector<int>>, int>>q;//board,dir;
	for (int i = 0; i < 4; i++)
		q.push({ board,i });

	int level = 0;
	while (true) {
 		if (level == 5)
		{
			int qsize = q.size();
			while (qsize--) {
				vector<vector<int>>adj = q.front().first;
				int dir = q.front().second;
				q.pop();
				for (int i = 0; i < adj.size(); i++)
					for (int j = 0; j < adj[i].size(); j++)   
						ans = max(ans, adj[i][j]);
			}
			cout << ans;
			return 0;
		}
		int qsize = q.size();
		while (qsize--) {
 			vector<vector<int>>adj = q.front().first;
			int dir = q.front().second;
			q.pop();

			move(adj, dir);

    		for (int i = 0; i < 4; i++)
				q.push({ adj, i });
		}
  		level++;
	}
}

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

문제

문제

출처

ICPC

BFS상태그래프로 구현했는데 틀렸습니다 도와주세요 ㅜㅜ

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말