글 읽기 - 이게 왜 통과를 못하는 걸까요?

nusung 7년 전 0

다양한 케이스를 만들어서 해봤을 땐, 통과인데

시간 에러가 나요...

가지치기를 햇는데 왜 에러가 나는 걸까요?

#include<iostream>
#include<string.h>
#include<deque>
using namespace std;
#pragma warning(disable:4996)
#define MAX 550
#define max(a,b) a>b?a:b

int D[MAX][MAX];
int A[MAX][MAX];
int N;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 }; // 좌 우 상 하

deque<pair<pair<int, int>,int>> dq;
pair<int, int> p;
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		for (int k = 1; k <= N; ++k)
			scanf("%d", &A[i][k]);
	// ----------------- 인풋 입력 완료

	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; j++) { // A[i][j] 로 접근 좌우->상하
		
			dq.push_back(make_pair(make_pair(j, i),1)); // 처음 좌표를 넣는다  x , y 기준
			
			D[i][j] = 1;
			while (!dq.empty()) {
				bool isPush = false;
				p = dq.back().first;
				int depth = dq.back().second;
				dq.pop_back(); // 들어있던 좌표 꺼내기

				int x = p.first;
				int y = p.second;

				
				for (int k = 0; k < 4; ++k) { // 좌 우 상 하  방향으로 정찰
					int nx = x + dx[k];
					int ny = y + dy[k];
					if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && A[y][x] < A[ny][nx]) { // 이동 가능하다.	
						if (D[ny][nx] > 1) { // 이미 계산했었다.												
							D[i][j] = max(D[i][j], depth+D[ny][nx]);
							continue;
						}
						if (!isPush) {
							//depth += 1;
							isPush = true;
						}
						pair<int, int> newp = make_pair(nx, ny);
						dq.push_back(make_pair(newp,depth+1));						
					}
				}
				if (!isPush) { // 네 방향으로 이동이 불가능 하다.
					D[i][j] = max(D[i][j], depth);
				}
				
			}// end dq.empty()

		} // end j
	}// end i
	
	int result = 0;
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= N; ++j)
			result = max(result, D[i][j]);
	cout << result << endl;
}

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

문제

문제

출처

ICPC

이게 왜 통과를 못하는 걸까요?

nusung 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말