> #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错了，还时间很长？ (802) csuyuanxing 2010-07-23 14:36:28