글 읽기 - 이동순서에 따라 시간초과여부가 결정납니다.

xkdlaldfjtnl 3년 전 0

여기서 이 코드가 맞게 나오는데 dx[4] 와 dy[4] 를

int dx[4] = { -1,0,1,0 }; => int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; => int dy[4] = { 0,1,0,-1 };

이렇게 선언해서 돌리면 시간 초과가 나옵니다.

제 생각에는 단순히 무엇을 먼저 조사한다고 해서 시간 초과/정상 작동으로 나뉘면 안될 것 같은데 다르게 나와서 질문 드립니다.

맞은 채점주소는

https://www.acmicpc.net/source/20485306

시간초과 채점주소는

https://www.acmicpc.net/source/20518903

입니다.

#include<iostream>
#include<utility>
#include<string>
using namespace std;
#define MAX 1001
int N, M, min_n = MAX * MAX;
int mat[MAX][MAX] = { 0 };
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
pair<int, int> p;
bool visited[MAX][MAX] = { false };
bool wall = false;
bool done = false;
void solve(int num, int i, int j) {
	if (min_n < num + (N - i + 1) + (M - j + 1))	return;
	if (i == N && j == M) {
		if (num < min_n) min_n = num;
		visited[i][j] = false;
		done = true;
		return;
	}
	for (int a = 0; a < 4; a++) {
		int x = i + dx[a];
		int y = j + dy[a];
		if (x < 1 || y < 1 || x > N || y > M || visited[x][y]) continue;
		if (!mat[x][y]) {
			visited[x][y] = true;
			solve(num + 1, x, y);
			visited[x][y] = false;
		}
		else if (!wall) {
			visited[x][y] = true;
			wall = true;
			solve(num + 1, x, y);
			wall = false;
			visited[x][y] = false;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	string str;
	for (int i = 1; i <= N; i++) {
		cin >> str;
		for (int j = 1; j <= M; j++) {
			mat[i][j] = str.at(j - 1) - '0';
		}
	}
	visited[1][1] = true;
	solve(1, 1, 1);
	if (done) cout << min_n << "\n";
	else cout << -1 << "\n";
	return 0;
}

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

문제

문제

출처

ICPC

이동순서에 따라 시간초과여부가 결정납니다.

xkdlaldfjtnl 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말