hdu 1010，一直超时，防课件写确实一直超时

hdu 1010，一直超时，防课件写的确一直超时
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
char map[8][8];
int n,m,t,k;
int si,sj,di,dj;
int dis[4][2]={{0,-1},{0,1},{1,0},{-1,0}}; 

void dfs(int si,int sj,int cnt)
{ int temp;
  if(si<=0||si>n||sj<=0||sj>m)return;
  if(si==di&&sj==dj&&cnt==t)
  {
  k=1;
  return;
  }
  temp=(t-cnt)-abs(si-di)-abs(sj-dj);
  if(temp<0||temp&1)return;
   
  for(int i=0;i<4;i++)
  {  
  if(map[si+dis[i][0]][sj+dis[i][1]]!='X')  
  { map[si+dis[i][0]][sj+dis[i][1]]='X';
  dfs(si+dis[i][0],sj+dis[i][1],cnt+1);
  map[si+dis[i][0]][sj+dis[i][1]]='.';
  }
  }
  return;
}

int main()
{
  while(cin>>n>>m>>t)
  {
  if(n==0&&m==0&&t==0)break;
  k=0;
  int wall=0;
  for(int i=1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
  cin>>map[i][j];
  if(map[i][j]=='S')
  {
  si=i;
  sj=j;
  }
  else if(map[i][j]=='D')
  { di=i;
  dj=j;
  }
  else if(map[i][j]=='X')
  wall++;  
  }
   
  if(m*n-wall<=t)
  {cout<<"NO"<<endl;
  continue;
  }
   
  map[si][sj]='X';
  dfs(si,sj,0);
  if(k==1)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  }
  system("pause");
  return 0;
  }
   


[解决办法]

C/C++ code

#include <iostream>#include <cmath>using namespace std;char maze[7][7];int N,M,T;int ptStartX,ptStartY,ptDoorX,ptDoorY;bool bFound;int Recur(int x,int y,int nLength){    char tmp;    if (bFound==false && maze[x][y]=='D' && nLength==T)    {        bFound=true;        cout<<"YES"<<endl;        return 0;    }    else if (bFound)    {        return 0;    }    if (nLength>T || ((T-nLength)-abs(x-ptDoorX)-abs(y-ptDoorY))%2!=0)    {        return -1;    }    tmp = maze[x][y];    maze[x][y]='X';    if (bFound==false && x-1>=0 && maze[x-1][y]!='S' &&  maze[x-1][y]!='X')    {        Recur(x-1,y,nLength+1);    }    if (bFound==false &&x+1<N && maze[x+1][y]!='S'&&  maze[x+1][y]!='X')    {        Recur(x+1,y,nLength+1);    }    if (bFound==false &&y-1>=0 && maze[x][y-1]!='S'&& maze[x][y-1]!='X')    {        Recur(x,y-1,nLength+1);    }    if (bFound==false &&y+1<M &&maze[x][y+1]!='S'&& maze[x][y+1]!='X')    {        Recur(x,y+1,nLength+1);    }    maze[x][y]=tmp;}int main(void){    int i,j;        do     {        bFound=false;        cin>>N>>M>>T;        if (N==0 && M==0 &&T==0)        {            break;        }        for (i=0;i<N;++i)            for (j=0;j<M;++j)            {                cin>>maze[i][j];                if (maze[i][j]=='S')                {                    ptStartX=i;                    ptStartY=j;                }                else if (maze[i][j]=='D')                {                    ptDoorX=i;                    ptDoorY=j;                }            }            Recur(ptStartX,ptStartY,0);            if (bFound==false)            {                cout<<"NO"<<endl;            }    } while (1);    return 0;} 
 
[解决办法]
以下2行将引起map数组下标超界(这可能是超时的原因）：
 for(int i=1;i<=n;i++)
 for(int j=1;j<=m;j++)
最好另外增加数组mark来标记是否搜索过，而不要用map数组来做标记。

以下修改可AC:
C/C++ code
#include<iostream>#include<string.h>#include<stdlib.h>using namespace std;char map[8][8];bool mark[8][8];//加int n,m,t,k;int si,sj,di,dj;int dis[4][2]={{0,-1},{0,1},{1,0},{-1,0}};  void dfs(int si,int sj,int cnt){ int temp;  if (k==1) return;  //if(si<=0||si>n||sj<=0||sj>m)return;  if(cnt==t)  {    if(si==di&&sj==dj)      k=1;     return;  }  temp=(t-cnt)-abs(si-di)-abs(sj-dj);    if(temp<0||(abs(si-di)+abs(sj-dj))%2!=(t-cnt)%2)return;//改if(temp<0||temp&1)return;      for(int i=0;i<4;i++)  {    int p=si+dis[i][0];    int q=sj+dis[i][1];  if(p>=0 && p<n && q>=0 && q<m && map[p][q]!='X' && mark[p][q]==0)  //改if(map[si+dis[i][0]][sj+dis[i][1]]!='X')    {      mark[p][q]=1; //改map[si+dis[i][0]][sj+dis[i][1]]='X';     dfs(p,q,cnt+1);//改dfs(si+dis[i][0],sj+dis[i][1],cnt+1);     mark[p][q]=0; //改map[si+dis[i][0]][sj+dis[i][1]]='.';  }  }  return;}int main(){  while(cin>>n>>m>>t)  {  if(n==0&&m==0&&t==0)break;  k=0;  int wall=0;  for(int i=0;i<n;i++)//错for(int i=1;i<=n;i++)  for(int j=0;j<m;j++)//错for(int j=1;j<=m;j++)  {  cin>>map[i][j];  if(map[i][j]=='S')  {  si=i;  sj=j;  }  else if(map[i][j]=='D')  { di=i;  dj=j;  }  else if(map[i][j]=='X')  wall++;     mark[i][j]=0;//加    }  if(m*n-wall<=t)  {cout<<"NO"<<endl;  continue;  }      mark[si][sj]=1;//改map[si][sj]='X';  dfs(si,sj,0);  if(k==1)cout<<"YES"<<endl;  else cout<<"NO"<<endl;  }  //system("pause");  return 0;  }