今天的一个哈密顿图 写了一个恶心的死搜

#include<string.h>
#include 
<stdio.h>

int m, n;
bool link[22][22];
bool v[22][22];

bool ll;
bool lll;
int bi,bj,ei,ej;
int c1;
void dfs(int i,int j)
{
    v[i][j]
=1;
                
if(i-1>=0 && v[i-1][j]==0 && link[i-1][j]==0)
                
{
                    dfs(i
-1,j);
                }

                
if(j-1>=0 && v[i][j-1]==0 && link[i][j-1]==0)
                
{
                    dfs(i,j
-1);
                }

                
if(i+1<&& v[i+1][j]==0 && link[i+1][j]==0)
                
{
                    dfs(i
+1,j);
                }

                
if(j+1<&& v[i][j+1]==0 && link[i][j+1]==0
                
{
                    dfs(i,j
+1);
                }

}


void DFS(int i,int j)
{

    
bool ss=0;
    v[i][j]
=1;    
    
bool vv[21][21];
    
int i1,j1;
    
for(i1=0;i1<n;i1++)
        
for(j1=0;j1<m;j1++)
            vv[i1][j1]
=v[i1][j1];

    v[i][j]
=0;
        
int ccc=0;
        
for(i1=0;i1<n;i1++)
            
for(j1=0;j1<m;j1++)
            
{
                
if(v[i1][j1]==0 && link[i1][j1]==0)
                
{
                
int cc=0;
                
if(i1-1>=0 && v[i1-1][j1]==0&& link[i1-1][j1]==0)
                    cc
++;
                
if(j1-1>=0 && v[i1][j1-1]==0&& link[i1][j1-1]==0)
                    cc
++;
                
if(i1+1<&& v[i1+1][j1]==0&& link[i1+1][j1]==0)
                    cc
++;
                
if(j1+1<&& v[i1][j1+1]==0&& link[i1][j1+1]==0)
                    cc
++;
                
if(cc==1)
                
{
                    ccc
++;
                }

                }

            }


    
bool con=1;

    
if(ccc>2)    con=0;

  v[i][j]
=1;
    

    
for(i1=0;i1<n;i1++)
        
for(j1=0;j1<m;j1++)
            
if(link[i1][j1]==0 && v[i1][j1]==0)
                dfs(i1,j1);

        
    
for(i1=0;i1<n;i1++)
        
for(j1=0;j1<m;j1++)
            
if(v[i1][j1]==0 && link[i1][j1]==0)
                con
=0;

    
for(i1=0;i1<n;i1++)
        
for(j1=0;j1<m;j1++)
            v[i1][j1]
=vv[i1][j1];
        

            
if(con)
            
{

                
if(i-1>=0 && v[i-1][j]==0 && link[i-1][j]==0)
                
{
                    
for(i1=0;i1<n;i1++)
                    
for(j1=0;j1<m;j1++)
                        v[i1][j1]
=vv[i1][j1];

                    DFS(i
-1,j);
                    ss
=1;
                }

                
if(j-1>=0 && v[i][j-1]==0 && link[i][j-1]==0)
                
{
                    
for(i1=0;i1<n;i1++)
                    
for(j1=0;j1<m;j1++)
                        v[i1][j1]
=vv[i1][j1];

                    DFS(i,j
-1);
                    ss
=1;
                }

                
if(i+1<&& v[i+1][j]==0 && link[i+1][j]==0)
                
{
                    
for(i1=0;i1<n;i1++)
                    
for(j1=0;j1<m;j1++)
                        v[i1][j1]
=vv[i1][j1];

                    DFS(i
+1,j);
                    ss
=1;
                }

                
if(j+1<&& v[i][j+1]==0 && link[i][j+1]==0
                
{
                    
for(i1=0;i1<n;i1++)
                    
for(j1=0;j1<m;j1++)
                        v[i1][j1]
=vv[i1][j1];

                    DFS(i,j
+1);
                    ss
=1;
                }


            
if(ss==0)
            
{
                ll
=1;
                
for(i1=0;i1<n;i1++)
                
for(j1=0;j1<m;j1++)
                
{
                    
if(v[i1][j1]==0 && link[i1][j1]==0)
                    
{
                        ll
=0;
                        i1
=n,j1=m;
                        
break;
                    }

                }

                
if(ll){
                    lll
=1;
                    
return;}

            }

            }

}



int main()
{

    
while(scanf("%d%d",&n,&m)==2)
    
{
        lll
=0;
        ll
=1;
        memset(v,
0,sizeof(v));
        
if(m==0 && n==0)break;
        
int i, j;
        
for(i=0;i<n;i++)
        
{
            
for(j=0;j<m;j++)
            
{
                scanf(
"%d",&link[i][j]);
            }

        }

        ei
=21,ej=21;
        c1
=0;
        
for(i=0;i<n;i++)
            
for(j=0;j<m;j++)
            
{
                
if(v[i][j]==0 && link[i][j]==0)
                
{
                
int cc=0;
                
if(i-1>=0 && v[i-1][j]==0&& link[i-1][j]==0)
                    cc
++;
                
if(j-1>=0 && v[i][j-1]==0&& link[i][j-1]==0)
                    cc
++;
                
if(i+1<&& v[i+1][j]==0&& link[i+1][j]==0)
                    cc
++;
                
if(j+1<&& v[i][j+1]==0 && link[i][j+1]==0)
                    cc
++;
                
if(cc==1)
                
{
                    bi
=i,bj=j;
                    c1
++;
                    i
=n,j=m;
                    v[bi][bj]
=1;
                    
break;
                }

                }

            }


        
for(i=0;i<n;i++)
            
for(j=0;j<m;j++)
            
{
                
if(v[i][j]==0 && link[i][j]==0)
                
{
                
int cc=0;
                
if(i-1>=0 && v[i-1][j]==0&& link[i-1][j]==0)
                    cc
++;
                
if(j-1>=0 && v[i][j-1]==0&& link[i][j-1]==0)
                    cc
++;
                
if(i+1<&& v[i+1][j]==0&& link[i+1][j]==0)
                    cc
++;
                
if(j+1<&& v[i][j+1]==0&& link[i][j+1]==0)
                    cc
++;
                
if(cc==1)
                
{
                    c1
++;
                    ei
=i,ej=j;
                    i
=n,j=m;
                    
break;
                }

                }

            }


            
if(c1==1 || c1==2)
            
{
                    memset(v,
0,sizeof(v));
                    DFS(bi,bj);
            }

            
if(c1==0)
            
{
                
for(i=0;i<n;i++)
                
{
                    
for(j=0;j<m;j++)
                    
{
                        
                        
if(link[i][j]==0)
                        
{
                            memset(v,
0,sizeof(v));
                            DFS(i,j);
                        }


                        
if(lll==1)
                        
{
                            i
=n,j=m;
                            
break;
                        }

                    }

                }

            }


        
if(lll)
            printf(
"Yes\n");
        
else
            printf(
"No\n");
    }

    
return 0;
}
原文地址:https://www.cnblogs.com/SQL/p/913608.html