关于DFS求最优解
查看原帖
关于DFS求最优解
809165
The_Wandering_Earth楼主2023/3/23 20:48

rt,以P1747为例,如果在DFS函数中加上了行为1与列为1就return的结束条件就会无穷递归,去掉后就能AC,想问一下是为什么,AC代码如下:

#include <iostream>
#include <cstring>

using namespace std;

int x1, x2, y1, y2;
int step[55][55];
int dr[12] = {-2, -2, -2, -2, -1, 1, 2, 2, 2, 2, 1, -1};
int dc[12] = {-2, -1, 1, 2, 2, 2, 2, 1, -1, -2, -2, -2};

void dfs(int row, int col, int sum);

signed main(){
	memset(step, 127, sizeof(step));
    cin >> x1 >> y1;
    dfs(x1, y1, 0);
    cout << step[1][1] << endl;
    memset(step, 127, sizeof(step));
    cin >> x2 >> y2;
    dfs(x2, y2, 0);
    cout << step[1][1];
	return 0;
}

void dfs(int row, int col, int sum)
{
	//cout << row << " " << col << " " << sum << endl;
	if(sum >= step[row][col])
	{
		return;
	}
	step[row][col] = sum;
	for(int i = 0; i < 12; i++)
	{
		int r, c;
		r = row + dr[i], c = col + dc[i];
		if(r < 1 || r > 50 || c < 1 || c > 50)
		{
			continue;
		}
		dfs(r, c, sum + 1);
	}
}
2023/3/23 20:48
加载中...