1 条题解

  • 0
    @ 2021-6-15 12:50:57

    C++ :

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<ctime>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<vector>
    #include<queue>
    using namespace std;
    
    char m[10][10];
    int dir[][2] = {0,1, 1,0, -1,0, 0,-1};
    
    int sx, sy, tx, ty, t;
    bool flag;
    
    void dfs(int x, int y, int st) {
        if(flag) return;
        if(st == t) {
            if(x == tx && y == ty) flag = true;
            return;
        }
        int g = abs(x-tx) + abs(y-ty);
        if(g > (t - st)) return;
        if( (t-st-g) & 1 ) return;
        for(int i = 0; i < 4; ++i) {
            int xx = x + dir[i][0], yy = y + dir[i][1];
            if(m[xx][yy] == 'D') {
                if(st + 1 == t) { flag = true; return; }
                else continue;
            }
            if(m[xx][yy] == '.') dfs(xx, yy, st+1);
        }
    }
    
    int main() {
        int n, mm;
        //freopen("1.txt", "r", stdin);
        while(~scanf("%d%d%d", &n, &mm, &t)) {
            if(n == 0 && mm == 0 && t == 0) break;
    
            memset(m, 'X', sizeof(m));
            for(int i = 1; i <= n; ++i) scanf(" %s", m[i]+1), m[i][mm+1] = 'X';
    
            sx = tx = ty = sy = 0;
            for(int i = 1; i <= n; ++i) {
                for(int j = 1; j <= mm; ++j) {
                    if(m[i][j] == 'S') {
                        m[i][j] = '.';
                        sx = i, sy = j;
                    }
                    if(m[i][j] == 'D') {
                        tx = i, ty = j;
                    }
                }
            }
    
    
            if(sx == 0 || sy == 0 || tx == 0 || ty == 0) {
                puts("NO");
                continue;
            }
            flag = false;
            dfs(sx, sy, 0);
    
            //if( bfs(sx, sy, tx, ty, s) ) puts("YES");
            if( flag ) puts("YES");
            else puts("NO");
        }
        return 0;
    }
    
    
    • 1

    信息

    ID
    468
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者