朴素dfs会TLE，使用了记忆化搜索，但不知道哪里出了问题

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n, m;
int board[25][25];
int cnt;
int step[25][25];
int hr, hc;
class horse {
	public:
		int r;
		int c;
		horse(int r = 0, int c = 0) {
			this->r = r;
			this->c = c;
		}
		void move_all_directions() {
			int a[8][2] = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};
			for (int i = 0; i <= 7; i++) {
				if (r + a[i][0] >= 0 && c + a[i][1] >= 0) {
					board[r + a[i][0]][c + a[i][1]] = -1;
				}
			}
		}
};
class soldier {
	public:
		int r;
		int c;
		soldier(int r = 0, int c = 0) {
			this->r = r;
			this->c = c;
		}
		void move_down() {
			r += 1;
		}
		void move_right() {
			c += 1;
		}
		void move_up() {
			r -= 1;
		}
		void move_left() {
			c -= 1;
		}
};
int dfs(soldier& p);
bool judge(int r, int c) {
	if (board[r][c] == -1) {
		return false;
	} else if (r > n || c > m || r < 0 || c < 0) {
		return false;
	} else {
		return true;
	}
}
int main() {
	cin >> n >> m >> hr >> hc;
	horse h(hr, hc);
	board[hr][hc] = -1;
	h.move_all_directions();
	soldier p(0, 0);
	cout << dfs(p);
	return 0;
}
int dfs(soldier& p) {
	if (judge(p.r, p.c)==0) {
		return 0;
	} else if (step[p.r][p.c] != 0) {
		return step[p.r][p.c];
	} else if (p.r == n-1 && p.c == m) {
		return 1;
	} 
	else if (p.r==n&&p.c==m-1){
		return 1;
	}
	else if(p.r==n&&p.c==m){
		return 0;
	}
	else {
		p.move_down();
		step[p.r - 1][p.c] += dfs(p);
		p.move_up();
		p.move_right();
		step[p.r][p.c - 1] += dfs(p);
		p.move_left();
	}
}