连连看[HDU1175]

连连看

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 32234 Accepted Submission(s): 7955

Problem Description

“连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。
玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。

Input

输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)，分别表示棋盘的行数与列数。在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。
注意：询问之间无先后关系，都是针对当前状态的！

Output

每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。

Sample Input

3 4

1 2 3 4

0 0 0 0

4 3 2 1

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

1 1 2 4

1 3 2 3

0 0

Sample Output

YES

直接dfs就行，事实上，一开始自以为用来防止死循环的记录坐标是否搜索过的f数组是不应该存在的。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
int a[1005][1005];
bool f[1005][1005];
const int dx[4] = { -1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m, q;
bool dfs(int x1, int y1, int x2, int y2, int x, int y, int t) {
    if (t > 2 || x1 < 1 || x1 > n || y1 < 1 || y1 > m) {
        return false;
    }
    if (x1 == x2 && y1 == y2) {
        return true;
    }
    if (a[x1][y1] != 0) {
        if (x1 != x || y1 != y) {
            return false;
        }
    }
    for (int i = 0; i < 4; i++) {
        if (x1 - x == (-1 * dx[i]) && y1 - y == (-1 * dy[i])) {
            continue;
        }
        if (x1 == x + dx[i] && y1 == y + dy[i]) {
            if (dfs(x1 + dx[i], y1 + dy[i], x2, y2, x1, y1, t)) {
                return true;
            }
        } else {
            if (dfs(x1 + dx[i], y1 + dy[i], x2, y2, x1, y1, t + 1)) {
                return true;
            }
        }
    }
    return false;
}
int main() {
    while (scanf("%d%d", &n, &m)!=EOF) {
        if (n + m == 0) {
            break;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        scanf("%d", &q);
        int x1, x2, y1, y2;
        while (q--) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            memset(f, false, sizeof(f));
            if (a[x1][y1] != a[x2][y2] || a[x1][y1]*a[x2][y2] == 0 || (x2 < 1 || x2 > n || y2 < 1 || y2 > m) || (x1 == x2 && y1 == y2)) {
                printf("NO
");
            } else {
                if (dfs(x1, y1, x2, y2, x1, y1, -1)) {
                    printf("YES
");
                } else {
                    printf("NO
");
                }
            }
        }
    }
    return 0;
}

View Code