题目描述
题目思路
一开始想用动态规划，但是这道题没有明显的顺序性和递推关系可以找，起点也是自定义的，鉴于迷宫尺寸不大，考虑使用DFS或BFS。
在自己推算几遍后发现，假设可以在地图上畅通无阻，那么格子只有可能像棋盘一样排列：
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
用理想的格子与实际输入的图进行对比，找出存在差异的格子，这些格子便是不能通行的。
然后再从起点开始进行DFS/BFS，搜索出总共能够通行的格子数。
此外还有一个重要的优化，由于输入的起点个数极大，为，不可能每次输入起点都要重新进行一次搜索，因此对整个图的记忆化应该在输入起点之前就完成，这时输入起点坐标只需在直接给出二维数组中的对应结果即可。
我的代码
最开始我的dfs函数如下：
#include <iostream>
#include <algorithm>
using namespace std;
int map[1002][1002];
int ans[1002][1002];
int n;
int m;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int answer;
void dfs(int x, int y) {
ans[x][y]++;
answer++;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (ans[nx][ny] == 0 && map[x][y]==map[nx][ny]) {
dfs(nx, ny);
}
}
ans[x][y] = answer;
}
int main() {
int i;
int j;
cin >> n >> m;
//限定边界
for (i = 0; i <= n+1; i++)
{
map[i][n+1] = 2;
map[i][0] = 2;
map[0][i] = 2;
map[n+1][i] = 2;
}
//初始化地图
for (i = 1; i <= n; i++)
{
for ( j = 1; j <= n; j++)
{
char x = '1';
if ((i + j) % 2 == 0) {
x = '0';
}
char y;
cin >> y;
if (x == y) {
map[i][j] = 0;
}
else {
map[i][j] = 1;
}
}
}
//初始化每个格子的答案
for (int A = 0; A <= n + 1; A++)
{
for (int B = 0; B <= n + 1; B++)
{
ans[A][B] = 0;
}
}
//深度优先搜索
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++) {
if (ans[i][j] == 0) {
answer = 0;
dfs(i, j);
}
}
}
while (m--) {
int x;
int y;
cin >> x >> y;
cout << ans[x][y]<<endl;
}
return 0;
}代码测试了很多次没问题，样例也过了，可测试点全错误。仔细一看，果然还是递归函数写得有问题：在递归之前计数，answer自增；递归结束之后获取最终信息answer，看似合理，实则只能给搜索起点及周围的方格正确赋值，一旦接近递归边界，有些分支无法赋到正确的值。
这也给我了一个启示：如果要在DFS中计算总搜索格数或次数（或由叶子结点向上传递信息），最终获得完整信息的只能是根结点。
修改后使用栈容器存储搜索过的方格坐标，一次DFS彻底完成后再将搜索过的方格统一赋值。
正确代码：
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
stack<pair<int, int>> stk;
int map[1002][1002];
int ans[1002][1002];
int n;
int m;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int answer;
void dfs(int x, int y) {
ans[x][y]++;
answer++;
//对组入栈
pair<int, int> p(x, y);
stk.push(p);
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (ans[nx][ny] == 0 && map[x][y]==map[nx][ny]) {
dfs(nx, ny);
}
}
ans[x][y] = answer;
}
int main() {
int i;
int j;
cin >> n >> m;
//限定边界
for (i = 0; i <= n+1; i++)
{
map[i][n+1] = 2;
map[i][0] = 2;
map[0][i] = 2;
map[n+1][i] = 2;
}
//初始化地图
for (i = 1; i <= n; i++)
{
for ( j = 1; j <= n; j++)
{
char x = '1';
if ((i + j) % 2 == 0) {
x = '0';
}
char y;
cin >> y;
if (x == y) {
map[i][j] = 0;
}
else {
map[i][j] = 1;
}
}
}
//初始化每个格子的答案
for (int A = 0; A <= n + 1; A++)
{
for (int B = 0; B <= n + 1; B++)
{
ans[A][B] = 0;
}
}
//深度优先搜索
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++) {
if (ans[i][j] == 0) {
answer = 0;
dfs(i, j);
while (!stk.empty()) {
//储存过的坐标赋值并出栈
ans[stk.top().first][stk.top().second] = answer;
stk.pop();
}
}
}
}
while (m--) {
int x;
int y;
cin >> x >> y;
cout << ans[x][y]<<endl;
}
return 0;
}很有对于才学尚浅的我而言是一道很有营养的题目。
