i use dfs but getting tle plz help
Code: Select all
#include<stdio.h>
#include<string.h>
#include<memory.h>
#define MAX 100
char GAME[4][4];
bool MAP[4][4];
char c[134];
int reach[8][2]={{+0,+1},{+0,-1},{-1,+0},{-1,+1},{-1,-1},{+1,-1},{+1,+0},{+1,+1}},R,C,l,count=0;
void dfs(int i,int j,int depth){
if(GAME[i][j]!=c[depth])return ;
if(depth==(l-1)){
if(l==3)count++;
else if(l==4)count++;
else if(l==5)count+=2;
else if(l==6)count+=3;
else if(l==7)count+=5;
else count+=11;
return;
}
MAP[i][j]=false;
for(int k=0;k<8;k++){
if(i+reach[k][0]<0||i+reach[k][0]>=4||j+reach[k][1]<0||j+reach[k][1]>=4)continue;
if(MAP[i+reach[k][0]][j+reach[k][1]])dfs(i+reach[k][0],j+reach[k][1],depth+1);
}
MAP[i][j]=true;
}
int main(){
int i,q,n,m,w,x=0;
char ch[6];
gets(ch);
sscanf(ch,"%d",&w);
printf("\n");
for(q=0;q<w;q++){
memset(MAP,true,sizeof(MAP));
if(q)printf("\n");
count=0;
for(i=0;i<4;i++)
gets(GAME[i]);
gets(ch);
sscanf(ch,"%d",&n);
for(m=0;m<n;m++){
gets(c);
l=strlen(c);
for(i=0;i<4;i++)
for(int j=0;j<4;j++)
if(c[0]==GAME[i][j]){R=i;C=j;break;}
dfs(R,C,0);
}
x++;
printf("Score for Boggle game #%d: %d\n",x,count);
}
return 0;
}