深度优先搜索-迷宫问题（走迷宫题解）

题目描述

你正在玩一个迷宫游戏，迷宫有 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
", ans[i]);
	}
	return 0;
}