走迷宫题解

题目描述

你正在玩一个迷宫游戏，迷宫有 n×n 格，每一格有一个数字 0 或 1，可以从某一格移动到相邻四格中的一格上。为了消磨时间，你改变了玩法，只许从 0 走到 1 或者从 1 走到 0。
现在给你一个起点，请你计算从这个格子出发最多能移动多少个格子（包含自身）。

输入格式:
第1行包含两个正整数 n 和 m（1≤n≤1000,1≤m≤10000）。
接下来 n 行，对应迷宫中的 n 行，每行 n 个字符，字符为 0 或者 1，字符之间没有空格。
接下来 m 行，表示 m 次询问。每行 2 个正整数 i，j，表示从迷宫中第 i 行第 j 列的格子开始走。

输出格式:
输出共 m 行，每行一个整数，分别对应于输入数据中的 m 次询问，给出最多能移动的格子数。

完整代码

#include<stdio.h>
#include<string.h>

int n;
int x[1020][1020], ans[10020];
char c[1020][1020];

void dfs(int a, int b, int flag, int i) {
    if (a == 0 || a == n + 1 || b == 0 || b == n + 1 || 
        x[a][b] != -1 || c[a][b] - '0' != flag) {
        return;
    }/*搜索达到深度 或 已搜索 或 不满足1、0条件*/
    x[a][b] = i;
    ans[i]++;
    dfs(a - 1, b, !flag, i);
    dfs(a + 1, b, !flag, i);
    dfs(a, b - 1, !flag, i);
    dfs(a, b + 1, !flag, i);
}

int main()
{
    int m, i, j, a, b;
    scanf("%d%d", &n, &m);
    memset(x, -1, sizeof(x));
    for (i = 1; i <= n; i++) {
        getchar();
        for (j = 1; j <= n; j++) {
            scanf("%c", &c[i][j]);
        }
    }
    for (i = 1; i <= m; i++) {
        scanf("%d%d", &a, &b);
        if (x[a][b] == -1) {
            dfs(a, b, c[a][b] - '0', i);
        }/*未搜索*/
        else {
            ans[i] = ans[x[a][b]];
        }/*已搜索*/
        printf("%d\n", ans[i]);
    }
    return 0;
}

走迷宫题解

原文：https://www.cnblogs.com/dump16/p/12539960.html