글 읽기 - 배열에서 이동 틀리 부분을 찾기가 힘드네요. 제발 도와주세요.

simbaddaji 8년 전 0

이틀동안 매달려 있는데 틀린 예시나 어디가 틀렸는지 잘 모르겠습니다.

컴파일 시작하자마자 틀렸다고 뜹니다. 예시와 n이 2일때 n이 100일 때 모두 해보아도 맞는것 같습니다.

bs로 mid값을 찾아 bfs로 돌면서 최대값 최소값을 조사하다가 중간에 mid값 보다 크다면

queue에 push하지 않고 패스하는 방식입니다.

제발 도와주세요!

#include<stdio.h>
#include<queue>
using namespace std;

int n=0,map[101][101],smin,smax;
int visited[101][101];
bool bfs(int mid){
	queue<int> x;queue<int> y;queue<int> M;queue<int> m;
	x.push(0);y.push(0);M.push(map[0][0]);m.push(map[0][0]);
	visited[0][0]=0;
	while(!x.empty()){
		if(x.front()==n-1&&y.front()==n-1){return true;}

		if(x.front()-1>=0&&visited[x.front()-1][y.front()]==1){//여기
			if(M.front()<map[x.front()-1][y.front()])smax=map[x.front()-1][y.front()];
			else{smax=M.front();}
			if(m.front()>map[x.front()-1][y.front()])smin=map[x.front()-1][y.front()];
			else{smin=m.front();}
			if(smax-smin<=mid){
				x.push(x.front()-1);y.push(y.front());M.push(smax);m.push(smin);
				visited[x.front()-1][y.front()]=0;
			}
		}if(x.front()+1<n&&visited[x.front()+1][y.front()]==1){
			if(M.front()<map[x.front()+1][y.front()])smax=map[x.front()+1][y.front()];
			else{smax=M.front();}
			if(m.front()>map[x.front()+1][y.front()])smin=map[x.front()+1][y.front()];
			else{smin=m.front();}
			if(smax-smin<=mid){
				x.push(x.front()+1);y.push(y.front());M.push(smax);m.push(smin);
				visited[x.front()+1][y.front()]=0;
			}
		}if(y.front()-1>=0&&visited[x.front()][y.front()-1]==1){
			if(M.front()<map[x.front()][y.front()-1])smax=map[x.front()][y.front()-1];
			else{smax=M.front();}
			if(m.front()>map[x.front()][y.front()-1])smin=map[x.front()][y.front()-1];
			else{smin=m.front();}
			if(smax-smin<=mid){
				x.push(x.front());y.push(y.front()-1);M.push(smax);m.push(smin);
				visited[x.front()][y.front()-1]=0;
			}
		}if(y.front()+1<n&&visited[x.front()][y.front()+1]==1){
			if(M.front()<map[x.front()][y.front()+1])smax=map[x.front()][y.front()+1];
			else{smax=M.front();}
			if(m.front()>map[x.front()][y.front()+1])smin=map[x.front()][y.front()+1];
			else{smin=m.front();}
			if(smax-smin<=mid){
				x.push(x.front());y.push(y.front()+1);M.push(smax);m.push(smin);
				visited[x.front()][y.front()+1]=0;
			}
		}

		x.pop();y.pop();M.pop();m.pop();
	}
	return false;
}
int main(void){
	int l=0,r=0,mid=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			scanf("%d",&map[i][j]);
			if(map[i][j]>r)r=map[i][j];
		}
	}
	while(l<r){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				visited[i][j]=1;
			}
		}
		mid=(l+r)/2;
		if(bfs(mid)){r=mid;}
		else{l=mid+1;mid=l;}
	}
	printf("%d",mid);
	return 0;
}

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

문제

문제

출처

ICPC

배열에서 이동 틀리 부분을 찾기가 힘드네요. 제발 도와주세요.

simbaddaji 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말