글 읽기 - 제발 좀 도와주세요...ㅠㅠ

wjhappyboy 3년 전 0

아래와 같이 큐와 bfs 방식 이용해서 코드를 짰는데 틀렸습니다만 나오고 어떻게 틀렸는지 알수가 없어서

너무 답답해서 글을 올립니다 이게 dp 를 이용해서 한것이 맞는 지도 모르겠고요

어디가 문제인지, 반례가 있는지 좀 알려주세요..ㅠㅠ

#include<stdio.h>
#include<stdlib.h>
typedef struct queue{
    struct node* front;
    int size;
    struct node* rear;
}Queue;
typedef struct node{
    int height;
    int x;
    int y;
    struct node* link;
}Node;
int map(int M, int N, int** road);
void enqueue(Queue* head, int height, int x, int y);
void dequeue(Queue* head, int* x, int* y);
int main(void){
    int N, M, i, j, res;
    int** road;
    scanf("%d %d", &M, &N);
    road=(int**)malloc(sizeof(int*)*M);
    for(i=0; i<M; i++){
        *(road+i)=(int*)malloc(sizeof(int)*N);
    }
    for(i=0; i<M; i++){
        for(j=0; j<N; j++){
            scanf("%d", &road[i][j]);
        }
    }
    res=map(M, N, road);
    printf("%d\n", res);
    for(i=0; i<M; i++){
        free(*(road+i));
    }
    free(road);
    return 0;
}
int map(int M, int N, int** road){
    int** dir;
    Queue* head;
    int i, j, visit=0, x, y;
    dir=(int**)malloc(sizeof(int*)*M);
    for(i=0; i<M; i++){
        *(dir+i)=(int*)malloc(sizeof(int)*N);
    }
    for(i=0; i<M; i++){
        for(j=0; j<N; j++){
            *(*(dir+i)+j)=0;
        }
    }
    head=(Queue*)malloc(sizeof(Queue));
    head->size=0;
    head->front=NULL;
    head->rear=NULL;
    enqueue(head, *(*(road+0)+0), 0, 0);
    
    while(1){
        dequeue(head, &x, &y);
			  
        if(x==M-1&&y==N-1){
            visit++;
					
        }
        else{
            if(x-1>=0&&x-1<M){
                if(*(*(road+x-1)+y)<*(*(road+x)+y)){
                   
                    if(*(*(dir+x-1)+y)!=0){
                        visit=visit+*(*(dir+x-1)+y);
						*(*(dir+x)+y)=*(*(dir+x)+y)+1;
											
                    }
                    else{
                        enqueue(head, *(*(road+x-1)+y), x-1, y);
						*(*(dir+x)+y)=*(*(dir+x)+y)+1;
                    }
                }
            }
            if(x+1>=0&&x+1<M){
                if(*(*(road+x+1)+y)<*(*(road+x)+y)){
                    
                    if(*(*(dir+x+1)+y)!=0){
                        visit=visit+*(*(dir+x+1)+y);
						*(*(dir+x)+y)=*(*(dir+x)+y)+1;
											
                    }
                    else{
                        enqueue(head, *(*(road+x+1)+y), x+1, y);
						*(*(dir+x)+y)=*(*(dir+x)+y)+1;
                    }
                }
            }
            if(y-1>=0&&y-1<N){
                if(*(*(road+x)+y-1)<*(*(road+x)+y)){
                    
                    if(*(*(dir+x)+y-1)!=0){
                        visit=visit+*(*(dir+x)+y-1);
						*(*(dir+x)+y)=*(*(dir+x)+y)+1;
											
                    }
                    else{
                        enqueue(head, *(*(road+x)+y-1), x, y-1);
						*(*(dir+x)+y)=*(*(dir+x)+y)+1;
                    }
                }
            }
            if(y+1>=0&&y+1<N){
                if(*(*(road+x)+y+1)<*(*(road+x)+y)){
                    
                    if(*(*(dir+x)+y+1)!=0){
                        visit=visit+*(*(dir+x)+y+1);
						*(*(dir+x)+y)=*(*(dir+x)+y)+1;
											
                    }
                    else{
                        enqueue(head, *(*(road+x)+y+1), x, y+1);
						*(*(dir+x)+y)=*(*(dir+x)+y)+1;
                    }
                }
            }
        }
        if(head->size==0){
            break;
        }
		}
    free(head);
	
    for(i=0; i<M; i++){
        free(*(dir+i));
    }
    free(dir);
    return visit;
}
void enqueue(Queue* head, int height, int x, int y){
    Node* new;
    new=(Node*)malloc(sizeof(Node));
    new->height=height;
    new->x=x;
    new->y=y;
    new->link=NULL;
    if(head->size==0){
        head->front=new;
        head->rear=new;
    }
    else{
        head->rear->link=new;
        head->rear=new;
    }
    (head->size)++;
}
void dequeue(Queue* head, int* x, int* y){
    Node* temp;
    if(head->size==0){
        return;
    }
    else if(head->size==1){
        temp=head->front;
        (*x)=temp->x;
        (*y)=temp->y;
        head->front=NULL;
        head->rear=NULL;
        (head->size)--;
        free(temp);
    }
    else{
        temp=head->front;
        (*x)=temp->x;
        (*y)=temp->y;
        head->front=temp->link;
        (head->size)--;
        free(temp);
    }
}

mwy3055 3년 전 0

bfs보다는 dfs를 추천합니다.

경로의 수만 찾으면 되는 문제니까요.

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

문제

문제

출처

ICPC

제발 좀 도와주세요...ㅠㅠ

wjhappyboy 3년 전 0

mwy3055 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말