蓝桥杯基础练习VIP-回形取数-题解（C++代码）-dfs剪枝【思路比较清晰】

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int m, n;
int a[200][200];
int vis[200][200];
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};//下，右，上，左
bool check(int x, int y) //判断下个位置能不能走
{
	return (x>=0&&y>=0&&x < m&& y < n&& vis[x][y] != 1);
}
void dfs(int x, int y,int i,int j) //x，y当前坐标，i,j当前方向
{
	if (vis[x][y] == 0 && x == 0 && y == 0) cout << a[x][y];
	else if (vis[x][y] == 0) cout << " " << a[x][y];
	vis[x][y] = 1;
	int dx = x + i;
	int dy = y + j;
	if (check(dx, dy)) dfs(dx, dy, i, j);	//判断当前方向能不能走，不能就换方向
	else
	{
		for (int i = 0; i < 4; i++)
		{
			 dx = x + dir[i][0];
			 dy = y + dir[i][1];
			if (check(dx, dy))
			{
				dfs(dx, dy,dir[i][0],dir[i][1]);
				break; //减去此位置其他方向的可能
			}
		}
	}
}
int main()
{
	cin >> m >> n;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin>>a[i][j];
		}
	}
	dfs(0,0,1,0);
}