#include <cstdio>
#include <cstring>
//#include <conio.h>

const int MAXN=1000+5;
char maze[MAXN][MAXN];

int cnt;
int i;
int num;
int steps;
int R,S;


void dfs(int i,int j)
{
     if(++steps==R+S-2)
     {
      if(i==R-1&&j==S-1)num++;
      return;
     }
     
     if( maze[i+1][j]=='.' && i+1<R){dfs(i+1,j);steps--;}
     if( maze[i][j+1]=='.' && j+1<S){dfs(i,j+1);steps--;}
    
}
int main()
{
    
    
    //freopen("input.txt","r",stdin);
   
    scanf("%d",&cnt);
    while(cnt--)
    {
       scanf("%d%d\n",&R,&S);
	   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;
    
    
    
}

我改进成这样照样超时，难道只能dp？