글 읽기 - 재귀로 풀어서 예제 답은 맞게 나오는데 시간초과가 나옵니다

zelot11 4년 전 0

시간초과가 어디서 나는지 혹시 알려주실 수 있나용 ㅠ

//0 0 2
//1 1 2
//2 0 1 2 
int dy[]={0,1,1};

int dx[]={1,0,1};
int N;
int ans=0;
int direction[3][3]={1, 0 ,1, 0,1,1 , 1, 1,1};
int* copy(int map[16][16],int copymap[16][16])
{
    for( int y=0; y<N; y++)
    {
        for( int x=0; x<N; x++)
        {
            copymap[y][x]=map[y][x];
    }
    }
    return  (int*) copymap;
}
#include <iostream>
using namespace std;
void dfs(int y, int x, int state, int map[16][16])
{
    int copymap[16][16];
   // int copymap1[16][16];
    copy( map, copymap);
    
//    copy( copymap, copymap1);
    
    ////////////////////////////////////////////////////////////
    if( y>N-1 || x>N-1 || x<0 || y<0)
    {
    //    cout<<"ddddd"<<endl;
        return;
    }
    if( y==N-1 && x==N-1)
    {
        ans++;
     //   cout<<"count"<<endl;
        return;
    }
      //////////////////////////////////////////////////////////      
    for( int k=0; k<3; k++)
    {
        int yy;
        int xx;
     
     if(  direction[state][k]==0)
     {
         continue;
          
     }
     else
     {
       
        yy= y+dy[k];
        xx= x+dx[k];
           
        if( copymap[yy][xx]==1 || yy>N-1 || xx>N-1 ||xx<0|| yy<0 )
        {
              
           continue;
        }
        else if(k==2&& (copymap[yy][xx]+copymap[yy][xx-1]+copymap[yy-1][xx])>0 )
        {
            continue;
        }
        else
        {
            
            copymap[yy][xx]=1;
            
        }
     }

      
       
        dfs( yy,xx, k, copymap);
    

        copy( map, copymap);
        
    }
    //if(copymap)
};


int main()

{
    int map[16][16];
    cin>> N;

    for ( int yyy=0; yyy<N; yyy++)

    {

        for( int xxx=0; xxx<N; xxx++)

        {

         cin >>map[yyy][xxx];

        }

    }

   map[0][0]=1;
   map[0][1]=1;

      
   dfs( 0, 1,0, map);
 

 

 
 cout<<ans;
 

    return 0;

}

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

문제

문제

출처

ICPC

재귀로 풀어서 예제 답은 맞게 나오는데 시간초과가 나옵니다

zelot11 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말