定义状态 $f(i,j,0/1)$ ,表示左岸神父恶魔数量为$i,j$ ,右岸的数量自然就是 $n-i,n-j$ ,0/1 表示船此时停靠在哪边

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 105;
struct node{
	int x,y;
	int id;
};
int n,m; 
int vis[N][N][2]; //vis[i][j]表示到达状态<河的左岸神父数量为i,恶魔数量为j>的最小步数 ,0表示船在左岸 
node pre[N][N][2];//pre[i][j][0/1]表示到达状态(i,j,0/1)的上一个状态是谁 
bool check(int x,int y){
	if(x<0 || y<0 || x>n || y>n)return 0;
	if(x!=0 && x<y)return 0;
	if(x!=n && n-x<n-y)return 0;
	return 1;
}
void dfs(node now){
	if(now.x == n && now.y == n &&  now.id == 0){
		cout << vis[0][0][1] << "\n";
		return;
	}
	node las = pre[now.x][now.y][now.id];
	dfs(las);
	int xx = abs(now.x-las.x);
	int yy = abs(now.y-las.y);
	cout << xx << " " << yy << "\n";
}
void bfs(){
	memset(vis,-1,sizeof(vis));
	queue<node>q;
	q.push({n,n,0});
	vis[n][n][0] = 0;
	while(!q.empty()){
		node now = q.front();
		q.pop();
		if(now.x == 0 && now.y == 0 && now.id == 1)return;
		int x = now.x, y = now.y, id = now.id;
//		cout << x << " " << y << " " << id << endl;
		int nx,ny,nid = id^1;
		node nex;
		for(int sum = m;sum>=1;sum--){
			for(int dx = sum;dx>=0;dx--){
				int dy = sum-dx;
				if(dx && dx<dy)continue;//船上面神父被吃掉 
				if(id == 0){
					nx = x-dx;
					ny = y-dy;
				}
				else {
					nx = x+dx;
					ny = y+dy;
				}
				if(!check(nx,ny) || vis[nx][ny][nid]!=-1)continue; 
				vis[nx][ny][nid] = vis[x][y][id]+1;
				pre[nx][ny][nid] = now;
				q.push(node{nx,ny,nid});
			}
		}
		
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	bfs();
	if(vis[0][0][1] == -1)cout << -1;
	else dfs(node{0,0,1});
	return 0;
}