[HDU1728] 逃离迷宫

题目链接 Problem – 1728

最终在王学姐的助攻下A了……不简单啊……

一个深搜居然花了两天 12次提交后才A……

过两天把宽搜版本也顺便改下交掉……

一般深搜没有回溯或多或少都有一些问题
bfs状态记录不全也会有一些问题

嗯……下面贴代码……

#include 

using namespace std;

const int LEFT  = 0;
const int RIGHT = 1;
const int UP    = 2;
const int DOWN  = 3;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

char data[150][150];    // Storage the map.
int visited[150][150];  // The counter of how many times has we turned when we reach here
bool found;             // whether the solution is found or not
int m, n, k;            // the same meaning with the problem description

void dfs(int startx, int starty, int endx, int endy, int vec, int c = 0) {
    // Check if we has used up the chance.
    if (c > k) return;
    // Check if we has already reached here before.
    if (visited[starty][startx] < c) return;
    // Mark the position where we are located in.
    visited[starty][startx] = c;

    // Check if we reach (endx, endy) with vec
    int x = startx, y = starty; // (x, y) means where we are.
    for (;;) {
        x += dx[vec];
        y += dy[vec];
        // Check if we reach outside of the map or reach the block in the map.
        if (x < 0 || y < 0 || x >= n || y >= m || data[y][x] == '*')
            break;
        // Check if we reach (endx, endy)
        if (x == endx && y == endy) {
            found = true;
            return;
        }
    }
    // We did not reach the destination directly, so we should turn around at one corner and continue the test.
    x = startx, y = starty; // (x, y) means where we are.
    for (;;) {
        x += dx[vec];
        y += dy[vec];
        // Check if we reach outside of the map or reach the block in the map.
        if (x < 0 || y < 0 || x >= n || y >= m || data[y][x] == '*')
            break;
        // Let's turn at this corner.
        switch (vec) {
        case LEFT:
        case RIGHT:
            dfs(x, y, endx, endy, UP, c + 1);
            if (found) return;
            dfs(x, y, endx, endy, DOWN, c + 1);
            if (found) return;
            break;
        case UP:
        case DOWN:
            dfs(x, y, endx, endy, LEFT, c + 1);
            if (found) return;
            dfs(x, y, endx, endy, RIGHT, c + 1);
            if (found) return;
            break;
        }
        // Mark the place we are now.
        visited[y][x] = c;
    }
}

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        cin >> m >> n;
        for (int i = 0; i != m; ++i)
            cin >> data[i];
        int startx, starty, endx, endy;
        cin >> k >> startx >> starty >> endx >> endy;
        startx--, starty--, endx--, endy--;
        // Check if the starting point is the same as target.
        if (startx == endx && starty == endy) {
            cout << "yes" << endl;
            continue;
        }
        found = false;
        for (auto &i: visited)
            fill(i, i + 150, k);
        // The first step has no direction, just try the four direction one by one.
        for (int i = 0; i < 4; i++) {
            visited[starty][startx] = k;
            dfs(startx, starty, endx, endy, i);
            if (found) break;
        }
        if (found)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }
    return 0;
}