hdu 1728 逃离迷宫（DFS）

刚开始用连连看那道题的方法做的，一直超时，不知道怎么剪枝，在网上搜了别人的解法，大部分是BFS（看来这题BFS更简单，不过还没开始大量练习BFS，等学了BFS，再做一遍），也有DFS的解法，看了看，写了一个，代码如下：

#include <stdio.h>
#include <string.h>
int x_begin,y_begin,x_end,y_end;
char map[105][105];
int wan[105][105],f[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int n,m,flag,num;
void dfs(int x,int y,int d)
{
    if(wan[x][y] > num) return;
    if(x == x_end && y == y_end )
    {
        if(wan[x][y] <= num) flag = 1;
        return ;
    }
    if(wan[x][y] == num && x != x_end && y != y_end)
     return ;
    if(flag) return ;
    for(int i = 0 ; i < 4 ; i ++)
    {
        int dx = x + f[i][0];
        int dy = y + f[i][1];
        if(dx < 0 || dx >= n || dy < 0 || dy >= m)
         continue;
        if(map[dx][dy] == '*' || wan[dx][dy] < wan[x][y])
         continue;
        if(d != -1 && i != d && wan[dx][dy] < wan[x][y] + 1)
         continue;
         wan[dx][dy] = wan[x][y];
        if(d != -1 && i != d)
         wan[dx][dy] ++;
        dfs(dx,dy,i);
         if(flag)
          return ;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int T,i;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(i = 0 ; i < n ; i ++)
         scanf("%s",map[i]);
        scanf("%d%d%d%d%d",&num,&y_begin,&x_begin,&y_end,&x_end);
        x_begin--; y_begin--; x_end--; y_end--;
        memset(wan,1,sizeof(wan));
        flag = 0;
        wan[x_begin][y_begin] = 0;
        dfs(x_begin , y_begin , -1);
        if(flag) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

补充：软件开发 , C++ ,

上一个：两船载物问题
下一个：归并排序