#include <cstdio>
#include <iostream>
#include <cstring>
using std::cin;

//#include <conio.h>

const int MAXN=1000+1;
bool vis[MAXN][MAXN];
char maze[MAXN][MAXN];

int cnt;
int i,j,k;
int num;
int steps;
int R,S;
char s[MAXN+1];

bool dfs(int i,int j)
{
     if(!vis[i][j])vis[i][j]=true;
     else return false;
     
  
     if(++steps==R+S-2)
     {
      if(i==R-1&&j==S-1)num++;
      return true;
     }
    
     
     if( maze[i-1][j]=='.'&& i-1>=0 ){if(dfs(i-1,j)){vis[i-1][j]=false;steps--;}}
     if( maze[i][j-1]=='.' && j-1>=0 ){if(dfs(i,j-1)){vis[i][j-1]=false;steps--;}}
     if( maze[i+1][j]=='.'&& i+1<R){if(dfs(i+1,j)){vis[i+1][j]=false;steps--;}}
     if( maze[i][j+1]=='.'&& j+1<S){if(dfs(i,j+1)){vis[i][j+1]=false;steps--;}}
     return true;
}
int main()
{
    
    
    //freopen("input.txt","r",stdin);
   
    scanf("%d",&cnt);
    
    char ch;
    while(cnt--)
    {
       scanf("%d%d",&R,&S);
	   scanf("%c",&ch);
     
       for(i=0;i<R;i++)
      gets( *(maze+i) );
	 
      
       num=0;
       steps=-1;
       dfs(0,0);
       printf("Existuje %d ruznych cest.\n",num);
    }
    
    //getch();
    return 0;
    
    
    
}

• Re:为什么dfs错了，还时间很长？ (1377) csuyuanxing 2010-07-23 14:35:53
• Re:为什么dfs错了，还时间很长？ (1377) csuyuanxing 2010-07-23 14:35:54
  • Re:为什么dfs错了，还时间很长？ (802) csuyuanxing 2010-07-23 14:36:28