글 읽기 - c++ 90%에서 시간초과가 나고있습니다..

celestial 3년 전 0

이미 지나온 부분은 다시 검사할 필요가 없으니까

int ans = 0;

for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
visited[i][j] = true;
pair,char>start;
start.first.first = i;
start.first.second = j;
start.second = map[i][j];

Q.push(start);
ans+=BFS(start);

}
}

이런 식으로 이중 포문을 처음부터 돌지 않도록 조치해주었는데요,

그럼에도 어느 부분에서 잘못한 것인지 모르겠습니다.

입출력을 빨리 받는 것도 있다길래 입력해보았더니 그럼에도 여전히 90퍼센트에서 시간 초과가 나고 있군요.

조언을 주시면 정말 감사하겠습니다.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
#define MAX 501
using namespace std;


int N, M;
queue<pair<pair<int, int>,int>>Q;
char map[MAX][MAX];
bool visited[MAX][MAX];
int cnt = 0;
int BFS(pair<pair<int, int>,char> start) {

	while (!Q.empty()) {
		int x = Q.front().first.first;
		int y = Q.front().first.second;
		char z = Q.front().second;

		Q.pop();
		if (z == 'R') {
			y++;
			if (y >= M) { for (int i = 0; i < MAX; i++) {
				for (int j = 0; j < MAX; j++) {
					visited[i][j] = false;
				}
			}
			return 1; }
			if (visited[x][y]) { return 0; }
			 if (!visited[x][y]) {
				visited[x][y] = true;
				pair<pair<int, int>, char>next;
				next.first.first = x;
				next.first.second = y;
				next.second = map[next.first.first][next.first.second];
				Q.push(next);
			}
		}
		if (z == 'L') {
			y--;
			if (y < 0) {
				for (int i = 0; i < MAX; i++) {
					for (int j = 0; j < MAX; j++) {
						visited[i][j] = false;
					}
				}
				return 1; }
			if (visited[x][y]) { return 0; }
			if (!visited[x][y]) {
				visited[x][y] = true;
				pair<pair<int, int>, char>next;
				next.first.first = x;
				next.first.second = y;
				next.second = map[next.first.first][next.first.second];
				Q.push(next);
			}
		}
		if (z == 'U') {
			x--;
			if (x < 0) {
				for (int i = 0; i < MAX; i++) {
					for (int j = 0; j < MAX; j++) {
						visited[i][j] = false;
					}
				}
				return 1; }
			if (visited[x][y]) { return 0; }
			if (!visited[x][y]) {
				visited[x][y] = true;
				pair<pair<int, int>, char>next;
				next.first.first = x;
				next.first.second = y;
				next.second = map[next.first.first][next.first.second];
				Q.push(next);
			}
		}
		if (z == 'D') {
			x++;
			if (x >= N) {
				for (int i = 0; i < N; i++) {
					memset(visited[i], false, sizeof(bool) * M);
				}

				return 1; }
			if (visited[x][y]) { return 0; }
			if (!visited[x][y]) {
				visited[x][y] = true;
				pair<pair<int, int>, char>next;
				next.first.first = x;
				next.first.second = y;
				next.second = map[next.first.first][next.first.second];
				Q.push(next);
			}
		}



	}

}


int main()
{
	ios_base::sync_with_stdio(false);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}

	int ans = 0;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visited[i][j] = true;
			pair<pair<int, int>,char>start;
			start.first.first = i;
			start.first.second = j;
			start.second = map[i][j];

			Q.push(start);
			ans+=BFS(start);
			
		}
	}
	printf("%d ", ans);





}

qnsghd9999 2년 전 2

코드가 주석도 없어서 읽기가 솔직히 말하자면 좀 그래요 ㅠㅠ 힌트를 조금 드리겠습니다.

지나는 길이 무한으로 도는 곳이라면 다시 또다시 갈 필요 없으니깐 처리하잖아요??

그러면 지나는 길이 빠져나올 수 있는 길이라면 그 길도 다시 갈 필요가 없겠죠? 그 길도 처리를 해주시면 될 것 같아요~

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

문제

문제

출처

ICPC

c++ 90%에서 시간초과가 나고있습니다..

celestial 3년 전 0

qnsghd9999 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말