即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

gdufe acm 1068 Tempter of the Bone

编程语言 crazyboy12138 12℃ 0评论

题目链接:gdu 1068

题目大意:





一个N*M的迷宫,’S’为起点,’D’为终点,’X’为障碍,问能否恰好在T时刻到达终点。








判断能否恰好在某时刻或恰好走X步到达终点的搜索,


需要借助一个全局的flag变量来判断是否找到可行解。








本题的一个关键是剪枝:


如果已经找到可行解,或者已用时间大于T,退出当前dfs。



if(flag) return;


if(t >= k) return;

代码如下:

#include 
int n, m, k, flag;
int ma[10][10];
int vis[10][10];
int dx[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
inline bool check(int x, int y){
    if(x < 0 || x > n - 1 || y < 0 || y > m - 1 || ma[x][y] == 'X' || vis[x][y])
        return false;
    return true;
}
void dfs(int x, int y, int t){
    if(flag) return;
    if(t >= k) return;//这两行是剪枝,没有这两行会TLE
    if(t == k - 1){
        for(int i = 0; i < 4; i++){
            int xx = x + dx[i][0], yy = y + dx[i][1];
            if(check[xx][yy] && ma[xx][yy] == 'D'){
                flag = 1;
                return ;
            }
        }
        return ;
    }
    for(int i = 0; i < 4; i++){
        int xx = x + dx[i][0], yy = y + dx[i][1];
        if(check(xx, yy)){
            vis[xx][yy]  = 1;
            dfs(xx, yy, t + 1);
            vis[xx][yy] = 0;
        }
    }
}
int main(){
    while(scanf("%d%d%d", &n, &m, &k) == 3){
        if(n == 0 && m == 0 && k == 0) break;
        int xx, yy;
        flag = 0;
        getchar();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                scanf("%c", &ma[i][j]);
                if(ma[i][j] == 'S'){
                    xx = i; yy = j;
                }
            }
            getchar();
        }
        vis[xx][yy] = 1;
        dfs(xx, yy, 0);
        if(flag) puts("YES");
        else puts("NO");
    }
}

转载请注明:CodingBlog » gdufe acm 1068 Tempter of the Bone

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情