题目：点击打开链接
思路：
把河的对岸的情况用二进制存储，从右往左数第一位代表人是否在，其余的第i位代表第i+1只狗是否在。
先初始化0到2^(n+1)-1的所有符合条件的数，然后构造一个图，如果从a数和b数间的差异不超过m个不同并且奇偶不同，a数与b数就有一条边，找出最短路为所求。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;int n,m,k;
bool point[2500];int main() {scanf("%d%d%d",&m,&n,&k);int t=(1<<n+1)-1;if(m>n+1) m=n+1;for(int i=0; i<=t; i++) {point[i]=true;}for(int i=1; i<=k; i++) {int x,y;scanf("%d%d",&x,&y);int c=(1<<x)|(1<<y);for(int j=0; j<=t; j++) {if(point[j]==true) {if((j&c)==c&&j%2==0) {point[j]=false;point[(j^t)]=false;}}}}vector<int> point2;for(int i=0; i<=t; i++) {if(point[i]) {point2.push_back(i);}}int s=0;vector<int> a[2500];for(int i=0; i<point2.size(); i++) {for(int j=i+1; j<point2.size(); j++) {int x=point2[i]^point2[j];int s1=0;while(x!=0) {if(x%2==1) {s1++;}x/=2;}if(s1<=m) {if((point2[i]^point2[j])%2==1&&((point2[i]&point2[j])==point2[i]||(point2[i]&point2[j])==point2[j])) {a[i].push_back(j);a[j].push_back(i);}}}}int dis[2500]= {0};bool b[2500]= {0};for(int i=1; i<point2.size(); i++) {dis[i]=(1<<30);}b[0]=true;int x=0;for(int i=1; i<point2.size(); i++) {for(int j=0; j<a[x].size(); j++) {if(b[a[x][j]]==false&&dis[x]+1<dis[a[x][j]]) {dis[a[x][j]]=dis[x]+1;}}int Min=(1<<30);for(int j=0; j<point2.size(); j++) {if(b[j]==false&&dis[j]<Min) {x=j;Min=dis[j];}}b[x]=true;}if(dis[point2.size()-1]!=(1<<30)) {printf("%d",dis[point2.size()-1]);} else{printf("-1");}return 0;
}