글 읽기 - 1261 알고스팟문제 질문

nisroeld99 7년 전 0

메모이제이션으로 풀었는데

// 부분을 다시살리면 답이 잘못나옵니다..

6 6
001111
010000
001111
110001
011010
100010
입력시 3 나오네요 ..

물론 저거 지워버리면 2로 정답이 뜨긴하는데 시간초과가 뜹니다.

결국 dijkstra처럼해서 pq 에 넣어서 풀었는데

저기서 메모이제이션 적용이 안되는 이유가 뭘까요??

감사합니다

#include <iostream>
#include <algorithm>

using namespace std;
const int inf = 500000000;
int a[101][101];
int d[101][101];
bool c[101][101];
int n ,m;
int dy[4]= {0,-1,0,1};
int dx[4]= {-1,0,1,0};
int go (int ypos , int xpos){
    if (c[ypos][xpos])return inf;
    if (ypos < 1 || xpos < 1 || ypos > m || xpos > n) return inf ;
    int &ret = d[ypos][xpos];
    //if (ret  < inf )return ret;
    if (ypos == 1 && xpos ==1 ){
        return 0;
    }
    if ( a[ypos][xpos]==1 ){
        c[ypos][xpos]=true;
        for (int i = 0 ;i<4 ; i++){
            ret = min (ret ,go(ypos+dy[i] , xpos+dx[i])+1);
        }
        c[ypos][xpos]=false;
    }
    else {
        c[ypos][xpos]=true;
        for (int i = 0 ;i<4 ; i++){
            ret =min( go(ypos+dy[i] , xpos+dx[i]) , ret ) ;
        }
        c[ypos][xpos]=false;
    }
    return ret ;
}
int main(){
    
    scanf("%d%d",&n,&m);  //x ,y
    for (int i = 1; i<=m; i++){
        string s;
        cin>>s ;
        for (int j= 0 ;j<n ;j++){
            a[i][j+1]=s[j]-48;
        }
    }
    for (int i = 1; i<= m; i++)
        for (int j= 1 ;j<=n ;j++){
            d[i][j] = inf ;
        }
    
    
    
    cout<<go(m,n)<<endl;
    
}

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

문제

문제

출처

ICPC

1261 알고스팟문제 질문

nisroeld99 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말