学步园

这几天遇到一道比较简单的dfs+小小剪枝。但我就是做了两天，唉~~硬伤丫

而且是写错变量名！！

最主要是写错变量名很多测试用例都能过。。。。。

/*
546MS	288K
*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
char maze[10][10];
int a[] = {-1,0,1,0};
int b[] = {0,1,0,-1};
int w,h,Starti,Startj,Endi,Endj;
int DFS(int si,int sj,int T)
{
    if(T==0 && si==Endi && sj==Endj)
    return 1;
    if(abs(Endi-si)+abs(Endj-sj) > T || (T-abs(Endi-si)-abs(Endj-sj))%2!=0)
    return 0;
    if(T<0)
    return 0;
    for(int i=0;i<4;i++)
    if(si+a[i]>=0 && si+a[i]<h && sj+b[i]>=0 && sj+b[i]<w && maze[si+a[i]][sj+b[i]] == '.')
    {
        maze[si+a[i]][sj+b[i]] = 'X';
        if(DFS(si+a[i],sj+b[i],T-1))
        return 1;
        else
        maze[si+a[i]][sj+b[i]] = '.';
    }
    return 0;
}        
           
int main()
{
    int t;   
    while(scanf("%d%d%d",&h,&w,&t) && h+w+t!=0)
    {
        getchar();
        for(int i=0;i<h;i++)
        {
            //scanf("%s",maze[i]);
            for(int j=0;j<w;j++)
            {
                maze[i][j] = getchar();
                if(maze[i][j] == 'S')
                {
                Starti = i;
                Startj = j;  //我居然把这个学成Endj。。。。。
                }   
                else if(maze[i][j] == 'D')
                {
                    Endi = i;
                    Endj = j;
                    maze[i][j] = '.';
                }     
            } 
            getchar(); 
        }    
            if(t>w*h-1)
            {
            printf("NO\n");
            continue;
            }    
            if(DFS(Starti,Startj,t)) 
            printf("YES\n");
            else
            printf("NO\n");
    }
    system("pause");
    return 0;
}         

下面是优化后的代码。。。

/*
46 MS	328 KB
*/
#include<stdio.h>
#include <iostream>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
char maze[10][10];
int a[] = {0,0,-1,1};
int b[] = {-1,1,0,0};
int w,h,Starti,Startj,Endi,Endj;
int DFS(int si,int sj,int T)
{
    if(T==0 && si==Endi && sj==Endj)
    return 1;
    else
  {
    if((abs(Endi-si)+abs(Endj-sj)) > T )
    return 0;
    /*if((T-abs(Endi-si)-abs(Endj-sj))%2!=0)
    return 0;*/
    /*if(T<0)
    return 0;*/
    
    for(int i=0;i<4;i++)
    if(maze[si+a[i]][sj+b[i]] == '.' && T>0)
    {
        maze[si+a[i]][sj+b[i]] = 'X';
        if(DFS(si+a[i],sj+b[i],T-1))
        return 1;
        maze[si+a[i]][sj+b[i]] = '.';
    }
  }    
    return 0;
}        
           
int main()
{
    int t,sum;   
    while(scanf("%d%d%d",&h,&w,&t) && h!=0 && w!=0 && t!=0)
    {
        //getchar();
        sum = 0;
        memset(maze,'X',sizeof(maze));
        for(int i=1;i<=h;i++)
        {
            //scanf("%s%*c",maze[i]);
            for(int j=1;j<=w;j++)
            {
                //scanf("%c",&maze[i][j]);
                cin>>maze[i][j];
                if(maze[i][j] == 'S')
                {
                Starti = i;
                Startj = j;
                }   
                else if(maze[i][j] == 'D')
                {
                    Endi = i;
                    Endj = j;
                    maze[i][j] = '.';
                }  
                
                if(maze[i][j] == '.')
                   sum++;
            } 
            //getchar(); 
        }    
            if(t>sum || (t+Starti+Startj+Endi+Endj)%2 == 1 )
            {
            printf("NO\n");
            //continue;
            } 
            else
        {  
            maze[Starti][Startj] = 'X'; 
            if(DFS(Starti,Startj,t)) 
            printf("YES\n");
            else
            printf("NO\n");
        }    
    }
    system("pause");
    return 0;
}