洛谷P1162

程序柯

810人浏览 · 2025-03-09 22:21:17

程序柯 · 2025-03-09 22:21:17 发布

法一：

#include<bits/stdc++.h>
using namespace std;
int n,a[100][100],vis[100][100];
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x, int y) {
    // 边界条件：如果超出范围或已访问，则停止递归
    if (x < 0 || x >= n + 2 || y < 0 || y >= n + 2 || vis[x][y] || a[x][y] != 0) {
        return; // 显式停止递归
    }

    // 标记当前点为已访问
    vis[x][y] = 1;
    a[x][y] = 3;

    // 递归遍历四个方向
    for (int i = 0; i < 4; i++) {
        dfs(x + d[i][0], y + d[i][1]);
    }

    // 回溯：撤销当前点的访问标记
    vis[x][y] = 0;
}
int main(){
	/*
		长度为n的正方矩阵,使被1包围的0变为2,最后打印出来 
	*/ 
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	dfs(0,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]==0){
				cout<<"2"<<" ";
			}
			if(a[i][j]==3){
				cout<<"0"<<" ";
			}
			if(a[i][j]==1){
				cout<<a[i][j]<<" ";
			}
		}
		cout<<"\n";
	}
	return 0;
}

为什么需要 `vis[x][y] = 0;`？

回溯算法的核心思想：
- 在回溯算法中，我们需要尝试所有可能的路径。
- 当一条路径走完后，需要撤销当前的选择（即“回溯”），以便尝试其他路径。
vis[x][y] = 1; 的作用：
- 在递归进入某个点 (x, y) 时，将其标记为已访问（vis[x][y] = 1;），避免重复访问。
vis[x][y] = 0; 的作用：
- 在递归返回时，撤销当前点的访问标记（vis[x][y] = 0;），以便其他路径可以重新访问该点。
- 如果没有这一步，某些点可能会被错误地标记为已访问，导致其他路径无法访问这些点。

具体例子

假设矩阵如下：

0 0 0
0 1 0
0 0 0

从 (0, 0) 开始，dfs 会尝试所有可能的路径。
如果没有 vis[x][y] = 0;，当一条路径走完后，某些点会保持已访问状态，导致其他路径无法访问这些点。
例如，如果 (1, 0) 被标记为已访问，那么从 (2, 0) 开始的路径就无法访问 (1, 0)，即使这条路径是合法的。

是否需要 `vis[x][y] = 0;` 取决于问题需求

在某些问题中，我们不需要回溯（例如，只需要找到一条路径或遍历所有点一次），此时可以省略 vis[x][y] = 0;。但在你的代码中，由于需要遍历所有可能的路径，因此必须加上 vis[x][y] = 0;。

总结

vis[x][y] = 0; 是回溯算法的关键步骤，用于撤销当前点的访问标记，以便其他路径可以重新访问该点。

如果你的问题需要尝试所有可能的路径，则必须加上 vis[x][y] = 0;。
法二（其实和法一差不多，但这里没有return）：

#include<bits/stdc++.h>
using namespace std;
int n,a[100][100],vis[100][100];
int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y){
	for(int i=0;i<4;i++){
		if(a[x+d[i][0]][y+d[i][1]]==0&&x+d[i][0]>-1&&x+d[i][0]<n+2&&y+d[i][1]>-1&&y+d[i][1]<n+2&&vis[x+d[i][0]][y+d[i][1]]==0){
			vis[x+d[i][0]][y+d[i][1]]=1;
			a[x+d[i][0]][y+d[i][1]]=3;
			dfs(x+d[i][0],y+d[i][1]);
			vis[x+d[i][0]][y+d[i][1]]=0;
		} 
	}
}
int main(){
	/*
		长度为n的正方矩阵,使被1包围的0变为2,最后打印出来 
	*/ 
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	dfs(0,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]==0){
				cout<<"2"<<" ";
			}
			if(a[i][j]==3){
				cout<<"0"<<" ";
			}
			if(a[i][j]==1){
				cout<<a[i][j]<<" ";
			}
		}
		cout<<"\n";
	}
	return 0;
}

没有return也可以停止dfs函数并返回值吗？

1. 递归函数的终止条件

递归函数的终止条件不一定要通过 return 来实现。递归的终止可以通过以下方式实现：

边界条件：当递归函数达到某种边界条件时，不再继续递归调用，函数会自然返回。
访问标记：通过标记某些状态（如 vis 数组）来避免重复访问，从而停止递归。

在法2代码中，dfs 函数的终止条件是通过以下方式实现的：

如果当前坐标 (x, y) 的四个相邻位置都不满足条件（即值为 1、超出边界或已访问过），则递归调用栈会逐渐返回，函数自然结束。

2. 返回值问题

法2的 dfs 函数是 void 类型，这意味着它不需要返回值。它的作用是通过递归遍历矩阵，并修改矩阵的值（将某些 0 改为 3）。因此，dfs 函数不需要返回值，它的目的是修改全局状态（即矩阵 a 和访问标记 vis）。

如果你希望 dfs 函数返回值（例如，返回某种状态或结果），则需要将函数改为非 void 类型，并在适当的地方使用 return 返回值。

3. 为什么没有 `return` 也能停止递归？

递归函数的停止并不依赖于 return，而是依赖于递归调用栈的结束。当递归函数不再满足递归条件时，递归调用栈会逐渐返回，函数自然结束。

例如：

void dfs(int x, int y) {
    // 边界条件：如果超出范围或已访问，则停止递归
    if (x < 0 || x >= n || y < 0 || y >= n || vis[x][y] || a[x][y] != 0) {
        return; // 停止递归
    }

    // 标记当前点为已访问
    vis[x][y] = 1;
    a[x][y] = 3;

    // 递归遍历四个方向
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}

在这个例子中，return 用于显式地停止递归。如果没有 return，递归也会在边界条件不满足时自然停止。

4. 法2代码中的问题

法2代码中没有显式的 return，但仍然可以停止递归，这是因为：

当 dfs 函数遍历完所有可能的相邻位置后，递归调用栈会逐渐返回，函数自然结束。
由于 dfs 是 void 类型，不需要返回值，因此不需要显式的 return。

5. 改进建议

为了代码的可读性和健壮性，建议在递归函数中显式地添加 return 语句，以明确终止条件。例如：

void dfs(int x, int y) {
    // 边界条件：如果超出范围或已访问，则停止递归
    if (x < 0 || x >= n + 2 || y < 0 || y >= n + 2 || vis[x][y] || a[x][y] != 0) {
        return; // 显式停止递归
    }

    // 标记当前点为已访问
    vis[x][y] = 1;
    a[x][y] = 3;

    // 递归遍历四个方向
    for (int i = 0; i < 4; i++) {
        dfs(x + d[i][0], y + d[i][1]);
    }
    vis[x][y] = 0; 
}

这样写不仅更清晰，还能避免潜在的逻辑错误。