글 읽기 - 시간초과 질문드립니다 ㅠㅠ

culture1123 5년 전 0

시간초과 뜨는데 시간 줄일 수 있는 방법 없을까요??

고민해봐도 잘 모르겠네요 ㅠㅠ

#include <iostream>

using namespace std;
int n, m, h;
int map[11][31];
int tflag = 0;
int ans;
void check()
{
	int startr = 1;
	int startc = 1;
	int r = startr;
	int c = startc;
	int flag = 1;
	
	while (flag)
	{
		//cout << "startr" << startr << "startc" << startc << endl;
		//cout << "r" << r << "c" << c << endl;
        //이동하기
		if (map[r][c] == 0)
		{
			r++;
		}
		else if (map[r][c] == 1)
		{
			r++;
			c++;
		}
		else if (map[r][c] == 2)
		{
			r++;
			c--;
		}
		// 끝 확인
		if (startc == n && r == h + 1)
		{
			if (c == startc)
			{
			//	cout << "tr" << r << "tc" << c << endl;
				tflag = 1;
				return;
			}

		}
        //다음단계이동
		if (r == h+1 && c == startc)
		{
			//cout << "com" << endl;
			//cout << "r" << r << "c" << c << endl;
			r = startr;
			startc = startc + 1;
			c = startc;
			//cout << "startr" << startr << "startc" << startc << endl;
			
		}
		else if (r == h+1 && c != startc)
		{
			flag = 0;
			return;
		}
	}
}
void dfs(int r, int c, int cnt)
{
	if (tflag == 1)
		return;
	if (cnt <= 3)
	{
		//cout << "cnt" << endl;
		check();
		if (tflag == 1)
		{	
			ans = cnt;
			return;
		}
	}
	if (cnt >= 4)
		return;
	for (int a = r; a <= h; a++)
	{
		for (int b = c; b < n; b++)
		{
			if (map[a][b] == 0 && map[a][b + 1] != 1 && map[a][b + 1] != 2 && map[a][b - 1] != 2)
			{
				map[a][b] = 1;
				map[a][b + 1] = 2;
				dfs(a,b,cnt + 1);
				if (tflag == 1)
					return;
				map[a][b] = 0;
				map[a][b + 1] = 0;
			}
		}
	}
}
int main()
{
	cin >> n >> m >> h;
	for (int i = 0; i < m; i++)
	{
		int x, y;
		cin >> x >> y;
		map[x][y] = 1;
		map[x][y + 1] = 2;
	}
	check();
	if (tflag == 1)
	{
		//cout << "Asdf" << endl;
		cout << 0 << endl;
		return 0;
	}
	
	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j < n; j++)
		{
			if (map[i][j] == 0 && map[i][j+1] != 1 && map[i][j+1] !=2 && map[i][j-1] !=2)
			{
				map[i][j] = 1;
				map[i][j + 1] = 2;
				dfs(i,j,1);
				map[i][j] = 0;
				map[i][j + 1] = 0;
			}
		}
	}
	if (tflag == 1)
	{
		//cout << "234214" << endl;
		cout << ans << endl;
		return 0;
	}
	else
		cout << -1 << endl;
	
	return 0;
}

jh05013 5년 전 0

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

시간초과 질문드립니다 ㅠㅠ

culture1123 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말