글 읽기 - 어느 경우에 틀렸는지 잘 모르겠습니다.

papaya0033 8년 전 0

어느 케이스에 틀린지 잘 모르겠습니다.

dp[i][j] 배열을 dp[i-1][j] , dp[i][j-1] 를 통해서 0,0 ->N,M 까지 차례로 채워 넣었는데요.

예제 테스트케이스는 답이 나오는데요. 어느 경우에 틀린지 잘 모르겠습니다.

#include <iostream>
#include <cstring>
using namespace std;
int fromX[101];
int fromY[101];
int toX[101];
int toY[101];
int roadN;
bool isRoad(int a,int b,int c,int d){
    for(int i=0;i<roadN;i++){
        if(a==fromX[i] && b==fromY[i] && c==toX[i] && d==toY[i])
            return false;
    }
    return true;
} //(a,b)->(c,d)길이 있으면 true, 공사중이면 false 
int main(){
    long long int dp[101][101];
    int x;
    int y;
    int a,b,c,d;
    cin>>x>>y>>roadN;
    int miniX=x+1;
    int miniY=y+1;
    for(int i=0;i<roadN;i++){
        cin>>a>>b>>c>>d;
        if(a>c){
            fromX[i]=c;
            fromY[i]=d;
            toX[i]=a;
            toY[i]=b;
        }
        if(a<c){
            fromX[i]=a;
            fromY[i]=b;
            toX[i]=c;
            toY[i]=d;
        }
        if(b>d){
            fromX[i]=c;
            fromY[i]=d;
            toX[i]=a;
            toY[i]=b;
        }
        if(d>b){
            fromX[i]=a;
            fromY[i]=b;
            toX[i]=c;
            toY[i]=d;
        }
        if(toX[i]==0&&fromX[i]==0){
            miniY=min(miniY,fromY[i]);
        }
        if(toY[i]==0&&fromY[i]==0){
            miniX=min(miniX,fromX[i]);
        }
        
    }
    memset(dp,0,sizeof(dp));
    for(int i=0;i<miniY;i++){
        dp[0][i]=1;
    }
    for(int j=0;j<miniX;j++){
        dp[j][0]=1;
    }
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
                dp[i][j]=0;
                if(isRoad(i-1,j,i,j)){ //(i-1,j)에서 (i,j)로 가는 경로가 존재한다면(공사중이 아니라면)
                    dp[i][j]+=dp[i-1][j];
                }
                if(isRoad(i,j-1,i,j)){//(i,j-1)에서 (i,j)로 가는 경로가 존재한다면(공사중이 아니라면)
                    dp[i][j]+=dp[i][j-1];
                }
        }
    }
    cout<<dp[x][y]<<endl;
    return 0;
}

crasy111 8년 전 0

0행과 0열에 초기화 해줄때 formX와 fromY 전까지가아니라 toX와 toY전까지를 1로 채워줘야되는거 아닌가요??

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

문제

문제

출처

ICPC

어느 경우에 틀렸는지 잘 모르겠습니다.

papaya0033 8년 전 0

crasy111 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말