马踏棋盘

思路：dfs或者bfs均可

bfs解法：

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
typedef long long ll;
typedef pair<int,int> PII;

int n,m;
int ans = 0;
int l[5] = {1,2,1,2};
int r[5] = {2,1,-2,-1};

void bfs(){
	queue<PII> q;
	q.push({1,1});
	while(!q.empty()){
		auto t = q.front();
		q.pop();
//		cout << t.first << ' ' <<t.second << '\n';
		if(t.first == m && t.second == n){
			ans ++;
		}
		else{
			for(int i = 0; i < 4; i ++){
				int x1 = t.first + l[i];
				int y1 = t.second + r[i];
				if(x1 >= 1 && x1 <= m && y1 >= 1 && y1 <= n){
					q.push({x1,y1});
				}
			}
//			cout << '\n';
		}
	}

}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	bfs();
	cout << ans;
	return 0;
}

dfs解法

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 110;
const int inf = INT_MAX;
typedef pair<int, int> PII;
/*---------------------------------------------------------------------------*/
int n, m;
bool st[N][N] = {false};
int ans;

int dx[] = {1, 1, 2, 2}, dy[] = {2, -2, 1, -1};

void dfs (int x, int y) {
	if (x == m && y == n) {
		ans ++;
		return;
	}
 	cout << x << " " << y << endl;
	st[x][y] = true;

	for (int i = 0; i < 4; i ++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 1 && nx <= m && ny >= 1 && ny <= n && !st[nx][ny]) {
			dfs (nx, ny);
		}
	}
		st[x][y] = false;

}

void solve(){
	cin >> n >> m;
	dfs (1, 1);
	cout << ans;
}
/*---------------------------------------------------------------------------*/
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//  int tt; cin >> tt; while(tt --) solve();
    solve();
    return 0;
}