本文主要是介绍洛谷 P1141 01迷宫 (dfs解决)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
有一个仅由数字 0 与 1 组成的 n×n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。
你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。
输入格式
第一行为两个正整数 𝑛,𝑚。
下面 𝑛 行，每行 𝑛 个字符，字符只可能是 0 或者 1，字符之间没有空格。
接下来 𝑚 行，每行两个用空格分隔的正整数 𝑖,𝑗，对应了迷宫中第 𝑖 行第 𝑗 列的一个格子，询问从这一格开始能移动到多少格。
输出格式
𝑚 行，对于每个询问输出相应答案。
这道题最优解是并查集，把这些01分块每个坐标的块所能达到的最大面积就是该坐标的答案，这里我们讲讲用dfs如何解决这个问题：
首先他的条件是这个格子是0那你只能上下左右移动，并且下一个格子必须是1（反之相反），那么这个地方就是这道题的坑点了，如果没有这个限制，这个题基本就是dfs的模板题目了，那有了这个限制就需要一些小技巧：
我们发现迷宫都是01组成的，在c++程序中你会发现如果a = 1,那么!a = 0,那么可以利用这个点，在每次搜索是都传入上一个点迷宫的"！值",这样一来只用判断这个点是否与他相等即可，代码如下：
#include <bits/stdc++.h>
using namespace std;int b[1005][1005],arr[100005];
char s[1005][1005];
int n,m;void dfs(int i,int j,int k,int index){if(i < 0 || i >= n || j < 0 || j >= n || b[i][j] != -1 || k != s[i][j] - '0') return;b[i][j] = index;arr[index] ++;dfs(i - 1,j,!k,index);dfs(i + 1,j,!k,index);dfs(i,j - 1,!k,index);dfs(i,j + 1,!k,index);
}int main()
{cin >> n >> m;memset(b,-1,sizeof(b));for(int i=0;i<n;i++){cin >> s[i];}for(int i=0,x,y;i<m;i++){cin >> x >> y;x --, y --;if(b[x][y] == -1) dfs(x,y,s[x][y] - '0',i);else arr[i] = arr[b[x][y]];}for(int i=0;i<m;i++){cout << arr[i] << endl;}return 0;
}加油
这篇关于洛谷 P1141 01迷宫 (dfs解决)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
