附代码：
Source Code

Problem: 3603  User: JiaJunpeng 
Memory: 112212K  Time: 16141MS 
Language: C++  Result: Accepted 

Source Code 
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<map>
#include<vector>
using namespace std;
vector <int>  adj[6][999997];
int r,c,cnt,MOD=999997,dirx[]={-1,1,0,0},diry[]={0,0,-1,1};
struct pp
{
    bool mat[20][20];
};
pp nw;
struct qq
{
     int id1,id2;
};
qq list[200],queue[200];
struct bl
{
       int num;
       short list[145][2];
       bool operator <(const bl &temp)const
       {
            return num<temp.num;
       }
};
int f[20][20],temp1,temp2,temp,ans[200][200][2],num[200],cont;
bool visit[13][13];
void bfs(int id1,int id2,pp nw)
{
     int i,j,s,p,q;
     queue[0].id1=id1;
     queue[0].id2=id2;
     visit[id1][id2]=true;
     temp1=temp2=0;
     temp=1;
     while(temp1<=temp2)
     {
         for(i=temp1;i<=temp2;i++)
         {
             for(j=0;j<4;j++)
             {
                id1=queue[i].id1+dirx[j];
                id2=queue[i].id2+diry[j];
                if(id1>=0&&id1<r&&id2>=0&&id2<c)
                {
                    if(visit[id1][id2]==false&&nw.mat[id1][id2]==0)
                    {
                        visit[id1][id2]=true;
                        queue[temp].id1=id1;
                        queue[temp++].id2=id2;
                    }
                }
             }
         }
         temp1=temp2+1;
         temp2=temp-1;
     }
}
bool t_dfs(int a[],int id1,int id2,int na[],int dir,pp now,int deep,int ndeep);
bool dfs(int a[],pp nw,int ndeep);
int main()
{
    int i,j,ncnt,a[5];
    scanf("%d%d",&r,&c);
    cnt=0;
    memset(f,-1,sizeof(f));
    for(i=0;i<r;i++) 
      for(j=0;j<c;j++)
      {
         scanf("%d",&nw.mat[i][j]);  
         if(nw.mat[i][j]==0)
         {
             list[cnt].id1=i;
             list[cnt].id2=j;
             f[i][j]=cnt++;
         }
      }
    memset(num,0,sizeof(num));
    cont=0;
    int orz=dfs(a,nw,0);
    if(orz>0)
    {
        printf("%d\n",cont);
        for(i=0;i<cont;i++)
        {
            printf("%d:",num[i]);
            for(j=0;j<num[i];j++)
               printf(" (%d,%d)",ans[i][j][0]+1,ans[i][j][1]+1);
            printf("\n");
        }
    }    
    return 0;
}
bool t_dfs(int a[],int id1,int id2,int na[],int dir,pp now,int deep,int ndeep)
{
     int i,j,x,y,id,b[6];
     ans[ndeep][deep][0]=id1;
     ans[ndeep][deep][1]=id2;
     now.mat[id1][id2]=1;
     x=id1+dirx[dir];
     y=id2+diry[dir];
     if(x<0||x>=r||y<0||y>=c)
     {
        ans[ndeep][deep+1][0]=x;
        ans[ndeep][deep+1][1]=y;
        num[ndeep]=deep+2;
        if(num[ndeep]>3)
        {
            if(dfs(b,now,ndeep+1))
               return true;
        }
        now.mat[id1][id2]=0;
        return false;
     }
     if(now.mat[x][y]==0)
     {
         if(t_dfs(a,x,y,na,dir,now,deep+1,ndeep))
              return true;
         now.mat[id1][id2]=0;
         return false;
     }
     else
     {
         for(i=0;i<4;i++)
         {
             x=id1+dirx[i];
             y=id2+diry[i];
             if(x<0||x>=r||y<0||y>=c)
             {
                ans[ndeep][deep+1][0]=x;
                ans[ndeep][deep+1][1]=y;
                num[ndeep]=deep+2;
                if(num[ndeep]>3)
                {
                   if(dfs(b,now,ndeep+1))
                      return true;
                }
             } 
             else if(now.mat[x][y]==0)
             {
                 if(t_dfs(a,x,y,na,i,now,deep+1,ndeep))
                     return true;
             }
         }
         now.mat[id1][id2]=0;
         return false;
     }
}
bool dfs(int a[],pp nw,int ndeep)
{
     int siz,value=0,i,j,s=0,cou=0,na[5],b[6],id,in=1000000000;
     pp now;
     bl block[20];
     a[0]=a[1]=a[2]=a[3]=a[4]=0;
     for(i=0;i<r;i++)
     {
        for(j=0;j<c;j++)
        {
          if(nw.mat[i][j]==0)
          {
             int id=f[i][j];
             a[id/30]+=(1<<(id%30));
          }
        }
     }
     /*
     printf("\n");
     for(i=0;i<r;i++)
     {
          for(j=0;j<c;j++)
             printf("%d ",nw.mat[i][j]);
          printf("\n");
     }
     printf("a=(%d %d %d %d %d)\n",a[0],a[1],a[2],a[3],a[4]);
     system("pause");
    */
     if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0)
     {
         cont=ndeep;
         return true;
     }
     for(i=4;i>=0;i--)
        value=(((long long)((1<<30)%MOD)*(long long)value)%MOD+a[i])%MOD;
     siz=adj[0][value].size();
     for(i=0;i<siz;i++)
     {
        for(j=0;j<5;j++)
        {
            if(adj[j][value][i]!=a[j])
               break;
        }
        if(j>=5)
           break;
     }
     if(i<siz)
        return adj[5][value][i];    
     memset(visit,false,sizeof(visit));
     for(i=0;i<r;i++)
       for(j=0;j<c;j++)
       {
           if(visit[i][j]==false&&nw.mat[i][j]==0)
           {
               bfs(i,j,nw);
               block[cou].num=temp;
               for(s=0;s<temp;s++)
               {
                   block[cou].list[s][0]=queue[s].id1;
                   block[cou].list[s][1]=queue[s].id2;
               }
               cou++;
           }
       }
     for(i=0;i<cou;i++)
     {
        int orz=0;
        for(j=0;j<block[i].num;j++)
        {
           if(block[i].list[j][0]==0)
              orz++;
           else if(block[i].list[j][0]==r-1)
              orz++;
           else if(block[i].list[j][1]==0)
              orz++;
           else if(block[i].list[j][1]==c-1)
              orz++;
        }
        if(in>block[i].num)
        {
            in=block[i].num;
            id=i;
        }
        if(orz<=1)
            return false;
     }
     swap(block[id],block[0]);
     for(i=0;i<block[0].num;i++)
     {                           
         if(block[0].list[i][0]==0)
         {
             memset(na,0,sizeof(na));
             now=nw;
             num[ndeep]=0;
             ans[ndeep][num[ndeep]][0]=-1;
             ans[ndeep][num[ndeep]++][1]=block[0].list[i][1];
             if(t_dfs(a,block[0].list[i][0],block[0].list[i][1],na,1,now,1,ndeep))
             {
                 for(j=0;j<5;j++)
                    adj[j][value].push_back(a[j]);
                 adj[5][value].push_back(1);
                 return true;
             }         
         }
         if(block[0].list[i][0]==r-1)
         {                                                                          
             memset(na,0,sizeof(na));
             now=nw;
             num[ndeep]=0;
             ans[ndeep][num[ndeep]][0]=r;
             ans[ndeep][num[ndeep]++][1]=block[0].list[i][1];
             if(t_dfs(a,block[0].list[i][0],block[0].list[i][1],na,0,now,1,ndeep))
             {
                 for(j=0;j<5;j++)
                    adj[j][value].push_back(a[j]);
                 adj[5][value].push_back(1);
                 return true;
             }         
         }
         if(block[0].list[i][1]==0)
         {                        
            memset(na,0,sizeof(na));
            now=nw;
            num[ndeep]=0;
            ans[ndeep][num[ndeep]][0]=block[0].list[i][0];
            ans[ndeep][num[ndeep]++][1]=-1;
            if(t_dfs(a,block[0].list[i][0],block[0].list[i][1],na,3,now,1,ndeep))
            {
                for(j=0;j<5;j++)
                    adj[j][value].push_back(a[j]);
                adj[5][value].push_back(1);
                return true;
            }
         }
         if(block[0].list[i][1]==c-1)
         {                   
             memset(na,0,sizeof(na));
             now=nw;
             num[ndeep]=0;
             ans[ndeep][num[ndeep]][0]=block[0].list[i][0];
             ans[ndeep][num[ndeep]++][1]=c;
             if(t_dfs(a,block[0].list[i][0],block[0].list[i][1],na,2,now,1,ndeep))
             {
                for(j=0;j<5;j++)
                    adj[j][value].push_back(a[j]);
                adj[5][value].push_back(1);
                return true;
             }
         }
     }
     for(j=0;j<5;j++)
           adj[j][value].push_back(a[j]);
     adj[5][value].push_back(0);
     return false;
}