글 읽기 - 14890 - 경사로 문제 62%에서 계속 틀리는데 예외가 있는건가요...

dronelover 6년 전 0

길을 갈수 없을때만 발견해서 최대 정답수에서 빼주었는데

테스트케이스도 다 맞고 극단적인 케이스도 몇개 만들어봤는데 문제가 없었습니다...

도와주십시오... ㅠ

코드를 무식하게 짜기는 했는데 주석으로 조금이나마 설명해두었습니다

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

int n;
int d[100][100];
int d2[100][100];
int l;


int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	scanf("%d %d", &n, &l);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			scanf("%d", &d[i][j]);
			d2[j][i] = d[i][j];
		}
	}
	int ans = 2*n;
	for (int i = 0; i < n; i++){
		int p = 0;
		for (int j = 0; j < n && p <= 0;j++){ 
			// p==1이라면 못가는 경우가 있으니까 바로 다음 줄 확인하러 감.
            // j번째 칸에서 k번째 칸과 비교하면서 루프 
            int cnt = 1;
			for (int k = j + 1; k < n; k++){
				if (d[i][j] == d[i][k]){ // 같은 높이 갯수 
					cnt++;
					if (p == -1) p = 0;
				}
				else if (abs(d[i][j] - d[i][k])>1){ // 높이 차이 2이상. 브레이크 
					p = 1;
					break;
				}
				else if (d[i][j] < d[i][k]){ // 올라가야한다
					if (p == -1) cnt--;
					if (cnt < l) {
						p = 1; // 경사로를 놔야하는 이전의 블록의 갯수가 l개 안되면 브레이크
						break;
					}
					else{ // 경사로를 놓을수 잇으면 놓고 경사로 길이만큼 j증가 
						if (p == -1) p = 0;
						j = j + l - 1;
						break;
					}
				}
				else if (d[i][j] > d[i][k]){// 내려가야한다
					int check = 0;
					if (k + l > n) { // 앞으로 내려가는 경사 놓을 칸이 없다. 브레이크 
						p = 1;
						break;
					}
					for (int z = 0; z < l; z++){
						if (d[i][k] != d[i][k + z]){
							check = 1;  
							break;
						}
					}
					if (check == 1){
						p = 1; // 내려가는 경사 놓을 칸 높이 다르다. 브레이크
						break;
					}
					else{ // 앞으로 놓을 칸도 충분 + 모두 높이 같으면 놓고 경사로 길이만큼 j증가
						j = j + l - 1;
						p = -1;
						break;
					}
				}
			}
		}
		if (p == 1) ans--; // p==1이라면 못가는거니까 ans에서 빼주기 
	}


	for (int i = 0; i < n; i++){ // i,j를 바꾼 d2배열로 똑같이 돌리기 
		int p = 0;
		for (int j = 0; j < n && p <= 0; j++){
			int cnt = 1;

			for (int k = j + 1; k < n; k++){
				if (d2[i][j] == d2[i][k]){ // 같은 높이 갯수 
					cnt++;
					if (p == -1) p = 0;
				}
				else if (abs(d2[i][j] - d2[i][k])>1){
					p = 1;
					break;
				}
				else if (d2[i][j] < d2[i][k]){ // 올라가야한다
					if (p == -1) cnt--;
					if (cnt < l) {
						p = 1; // l개 안되면 브레이크
						break;
					}
					else{
						if (p == -1) p = 0;
						j = j + l - 1;
						break;
					}
				}
				else if (d2[i][j] > d2[i][k]){// 내려가야한다
					int check = 0;
					if (k + l > n) { // 내려가는 경사 놓을 칸이 없다. 브레이크 
						p = 1;
						break;
					}
					for (int z = 0; z < l; z++){
						if (d2[i][k] != d2[i][k + z]){
							check = 1;
							break;
						}
					}
					if (check == 1){
						p = 1; // 내려가는 경사 놓을 칸 높이 다르다. 브레이크
						break;
					}
					else{
						j = j + l - 1;
						p = -1;
						break;
					}
				}
			}
		}
		if (p == 1) ans--;
	}



	printf("%d", ans);

	
	
	return 0;
}

hyeonik7 6년 전 0

222111222 와 같은 상황일때 l = 2 인 조건이라면 경사로를 처음에 내려올땐 놓을 수 있지만, 다시 올라갈때는 경사로를 둘수 없어서 통과 불가능한 경로인데 올려주신 소스에서는 이런 케이스 점검 안하는것 같네요

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

문제

문제

출처

ICPC

14890 - 경사로 문제 62%에서 계속 틀리는데 예외가 있는건가요...

dronelover 6년 전 0

hyeonik7 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말