글 읽기 - 88퍼센트에서 틀립니다... 반례나 틀린부분 지적해주십시오...

juhongkim2 6년 전 0

맵에서 이동할 수 있는 칸 중에 레벨제한이 낮은 칸을 우선적으로 탐색하도록 우선순위큐를 이용해서

탐색해줬습니다

88퍼센트에서 틀리는데 반례나 틀린부분 있으면 조언부탁드립니다...

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

typedef struct{
	int xpos,ypos,dir,cnt,val;
}Pos;

int N,M,ans,k[101][101];
bool check[101][101][2];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
priority_queue <Pos> pq;

bool operator<(Pos p1, Pos p2)
{
	if(p1.val>p2.val)
		return true;

	return false;
}

int Max(int n1, int n2)
{
	if(n1>n2)
		return n1;

	return n2;
}

int IsinRange(int x, int y)
{
	if(x<0 || y<0 || x>=M || y>=N)
		return 0;

	return 1;
}

int main()
{
	int i,j,tx,ty;
	Pos in,out;

	scanf("%d %d",&N, &M);

	for(i=0;i<N;i++){
		for(j=0;j<M;j++){
			scanf("%d",&k[i][j]);
		}
	}

	for(i=1;i<=2;i++){
		in.xpos=0;
		in.ypos=0;
		in.dir=i;
		in.cnt=0;
		in.val=k[0][0];
		pq.push(in);
	}

	while(!pq.empty()){
		out=pq.top();
		pq.pop();
		//check[out.ypos][out.xpos][out.cnt]=true;
		ans=Max(ans,out.val);

		if(out.xpos==M-1 && out.ypos==N-1)
			break;

		for(i=0;i<4;i++){
			tx=out.xpos+dx[i]*2;
			ty=out.ypos+dy[i]*2;

			if(out.dir==i && out.cnt==0 && IsinRange(tx,ty)==1 && !check[ty][tx][out.cnt+1]){
				in.xpos=tx;
				in.ypos=ty;
				in.dir=i;
				in.cnt=out.cnt+1;
				in.val=k[ty][tx];
				pq.push(in);
				check[ty][tx][in.cnt]=true;
			}

			tx=out.xpos+dx[i];
			ty=out.ypos+dy[i];
			if(IsinRange(tx,ty)==1 && !check[ty][tx][out.cnt]){
				in.xpos=tx;
				in.ypos=ty;
				in.dir=i;
				in.cnt=out.cnt;
				in.val=k[ty][tx];
				pq.push(in);
				check[ty][tx][in.cnt]=true;
			}
		}
	}

	printf("%d\n",ans);

	return 0;
}

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

문제

문제

출처

ICPC

88퍼센트에서 틀립니다... 반례나 틀린부분 지적해주십시오...

juhongkim2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말