2625 - H. 跳格子

Solution 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;
}