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);
}
}