글 읽기 - 시간초과를 해결하고 싶습니다.

sejungpk 5년 전 0

열, 행 포함해서 8줄의 타일을 움직일 수 있기 때문에

0 ~ 3은 행

4 ~ 7은 열로 해서 모든 경우의 수를 생각해줬습니다.

하지만 이는 시간이 너무 걸리는 작업이기 때문에 중간에 어떤 검사를 해줘야할 것 같은데

어떻게 해야될지 감이 안잡힙니다...

#include<iostream>
#include<deque>
#include<vector>
using namespace std;

typedef struct Mtd
{
	int ic; //열 아님 행
	int idx; // 몇번째 행인지 아니면 열인지
	int move; //몇 칸 움직였는지

public:
	Mtd() {}
	Mtd(int ic, int idx, int move) :ic(ic), idx(idx), move(move) {}
};

deque<int> map[4];
vector<Mtd> mV;
vector<Mtd> ansV;
bool visit[8]; // 방법은 7개 이하다
bool flag = false; //더 이상 할 필요없다.
void Print()
{
	for (int n = 0; n < 4; n++)
	{
		for (int m = 0; m < 4; m++)
		{
			cout << map[n][m] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

bool update() //확인용
{
	int cnt = 1;
	for (int n = 0; n < 4; n++)
	{
		for (int m = 0; m < 4; m++)
		{
			if (map[n][m] == cnt)
			{
				cnt++;
				continue;
			}
			else
				return false;
		}
	}
	return true;
}

void Dfs(vector<Mtd> &v, int cnt, int maxCnt)
{
	if (flag)
		return;

	if (v.size() == maxCnt)
	{
		if (map[3][3] == 16 && map[0][0] == 1 && map[1][3] == 8)
		{
			cout << "cnt : " << cnt << endl;
			Print();
			if (update())
			{
				flag = true;
				ansV.swap(mV);
				return;
			}
		}
		return;
	}

	for (int idx = 0; idx < 8; idx++)
	{
		if (flag)
			break;

		int k = 1;
		if (!visit[idx])
		{
			visit[idx] = true;
			if (idx >= 0 && idx <= 3)
			{
				while (true)
				{
					if (k == 4 || flag)
					{
						break;
					}

					int tArray[4];
					for (int a = 0; a < 4; a++)
						tArray[a] = map[a][idx];

					for (int i = 1; i <= k; i++)
					{
						for (int j = 1; j < 4; j++)
						{
							map[j][idx] = tArray[j - 1];
						}
						map[0][idx] = tArray[3];

						for (int a = 0; a < 4; a++)
							tArray[a] = map[a][idx];
					}

					v.push_back(Mtd(2, idx, k));
					Dfs(v, cnt + 1, maxCnt);
					for (int i = 1; i <= k; i++)
					{
						for (int j = 0; j < 3; j++)
						{
							map[j][idx] = tArray[j + 1];
						}
						map[3][idx] = tArray[0];

						for (int a = 0; a < 4; a++)
							tArray[a] = map[a][idx];
					}
					k++;
					if (!v.empty())
						v.pop_back();
				}
				visit[idx] = false;
			}
			else if (idx >= 4 && idx <= 7)
			{
				while (true)
				{
					if (k == 4 || flag)
					{
						break;
					}

					for (int i = 1; i <= k; i++)
					{
						int tmp = map[idx % 4].back();
						map[idx % 4].pop_back();
						map[idx % 4].push_front(tmp);
					}

					v.push_back(Mtd(1, idx % 4, k));
					Dfs(v, cnt + 1, maxCnt);
					for (int i = 1; i <= k; i++)
					{
						int tmp = map[idx % 4].front();
						map[idx % 4].pop_front();
						map[idx % 4].push_back(tmp);
					}
					k++;
					if (!v.empty())
						v.pop_back();
				}
				visit[idx] = false;
			}
		}
	}
}


// 출력해야할것, 횟수, 타일을 움직이는 방법
// 1 - 
int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	//freopen("Text.txt","r", stdin);
	for (int n = 0; n < 4; n++)
	{
		for (int m = 0; m < 4; m++)
		{
			int num = 0;
			cin >> num;
			map[n].push_back(num);
		}
	}

	for (int i = 1; i <= 7; i++) //최소 한번 최대 일곱번
	{
		Dfs(mV, 0, i);

		if (flag)
			break;

		flag = false;
	}

	//출력
	cout << ansV.size() << endl;
	for (int i = 0; i < ansV.size(); i++)
	{
		cout << ansV[i].ic << " " << ansV[i].idx + 1 << " " << ansV[i].move << endl;
	}

	return 0;
}

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

문제

문제

출처

ICPC

시간초과를 해결하고 싶습니다.

sejungpk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말