HDU 1175 连连看 (DFS)

HDU 1175 连连看 (DFS)

题目：给出连连看棋盘，然后有q次询问，每次询问4个数(x1,y1,x2,y2)，输出是否能不绕外面且转折不超过两次消除，输出YES/NO

Sample Input

3 4
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4
1 1 2 4
1 1 3 3
2 1 2 4
3 4
0 1 4 3
0 2 4 1
0 0 0 0
2
1 1 2 4
1 3 2 3
0 0

Sample Output

YES
NO
NO
NO
NO
YES

#include <cstdio>
#include <cstring>
int table[1002][1002];
int dir[4][2] = { {-1,0}, {0, 1}, {1, 0}, {0, -1} };
int n, m, count;
int x2, y2;
bool ok;
bool check(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return false;
    if (x == x2 && y == y2) return true;
    else if (!table[x][y]) return true;
    else return false;
}
void dfs(int x1, int y1, int predir) {
    if (count == 3) {
        ok = false;
        return;
    }
    if (x1 == x2 && y1 == y2) {
        ok = true;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int newx = x1 + dir[i][0];
        int newy = y1 + dir[i][1];
        if (check(newx, newy)) {
            if (newx == x2 && newy == y2);
            else table[newx][newy] = 1;
            if (i == predir || predir == -1) {
                dfs(newx, newy, i);
            }
            else {
                count++;
                dfs(newx, newy, i);
                count--;
            }
            if (newx == x2 && newy == y2);
            else table[newx][newy] = 0;
            if (ok) return;
            
        }
    }
}
int main() {
    while (scanf("%d%d", &n, &m)) {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &table[i][j]);
            }
        }
        int q, x1, y1;
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            ok = false;
            count = 0;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x1--;
            y1--;
            x2--;
            y2--;
            if (table[x2][y2] && table[x1][y1] == table[x2][y2]) {
                dfs(x1, y1, -1);
            }
            printf("%s\n", ok ? "YES" : "NO");
        }
    }
    return 0;
}