#includeiostream
创新互联公司是一家网站设计公司，集创意、互联网应用、软件技术为一体的创意网站建设服务商，主营产品：响应式网站设计、品牌网站建设、成都营销网站建设。我们专注企业品牌在网站中的整体树立，网络互动的体验，以及在手机等移动端的优质呈现。成都网站建设、网站制作、移动互联产品、网络运营、VI设计、云产品.运维为核心业务。为用户提供一站式解决方案，我们深知市场的竞争激烈，认真对待每位客户，为客户提供赏析悦目的作品，网站的价值服务。
using namespace std;
int const Max = 16;
int dir[][2] = { { 1, 0 }, { 0, 1 } } ;
int dp[Max][Max] = { 0 };
int k = 0; //计数器
struct Point {
int x, y;
};
Point b, horse;
bool onboard(int x, int y) {
return x=0 xMax y=0 yMax;
}
void on(int x, int y) //将马附近的坐标记作1
{
if(onboard(x,y)) dp[x][y] = 1;
if(onboard(x-2,y-1)) dp[x - 2][y - 1] = 1;
if(onboard(x-2,y+1)) dp[x - 2][y + 1] = 1;
if(onboard(x+2,y-1)) dp[x + 2][y - 1] = 1;
if(onboard(x+2,y+1)) dp[x + 2][y + 1] = 1;
if(onboard(x-1,y-2)) dp[x - 1][y - 2] = 1;
if(onboard(x-1,y+2)) dp[x - 1][y + 2] = 1;
if(onboard(x+1,y-2)) dp[x + 1][y - 2] = 1;
if(onboard(x+1,y+2)) dp[x + 1][y + 2] = 1;
}
void dfs(int x, int y) {
if(x b.x || y b.y) return; // 如果提速，加上这行
if (x == b.x y == b.y) {
++k;
return;
}
for (int i = 0; i 2; i++) {
int IX = x + dir[i][0];
int IY = y + dir[i][1];
if (onboard(IX, IY)) {
if (dp[IX][IY] == 0) {
dfs(IX, IY);
}
}
}
}
int main() {
cin b.x b.y horse.x horse.y;
on(horse.x, horse.y);
dfs(0, 0);
cout k;
}
#includeiostream
using namespace std;
int const Max = 16;
int const dir[][2] = { { 1, 0 }, { 0, 1 } } ;
int dp[Max][Max] = { 0 };
int k = 0; //计数器
struct Point {
int x, y;
};
Point b, horse;
bool onboard(Point p) {
return p.x=0 p.xMax p.y=0 p.yMax;
}
void on(Point p) //将马附近的坐标记作1
{
int x = p.x, y = p.y;
if(onboard({x,y})) dp[x][y] = 1;
if(onboard({x-2,y-1})) dp[x - 2][y - 1] = 1;
if(onboard({x-2,y+1})) dp[x - 2][y + 1] = 1;
if(onboard({x+2,y-1})) dp[x + 2][y - 1] = 1;
if(onboard({x+2,y+1})) dp[x + 2][y + 1] = 1;
if(onboard({x-1,y-2})) dp[x - 1][y - 2] = 1;
if(onboard({x-1,y+2})) dp[x - 1][y + 2] = 1;
if(onboard({x+1,y-2})) dp[x + 1][y - 2] = 1;
if(onboard({x+1,y+2})) dp[x + 1][y + 2] = 1;
}
void dfs(Point current) {
int x = current.x, y = current.y;
if(x b.x || y b.y) return; // 如果提速，加上这行
if (x == b.x y == b.y) {
++k;
return;
}
for (int i = 0; i 2; i++) {
int IX = x + dir[i][0];
int IY = y + dir[i][1];
if (onboard({IX, IY})) {
if (dp[IX][IY] == 0) {
dfs({IX, IY});
}
}
}
}
int main() {
cin b.x b.y horse.x horse.y;
on(horse);
dfs({0, 0});
cout k;
}
递归算法，适合m、n 较小的情况。仅供参考：
const
m=13; n=15;
var
num:longint;
procedure next(x,y:integer);
begin
if (x=m)and(y=n) then begin
inc(num);
if num10000000 then begin
writeln('路径太多，请采用更优算法');
halt;
end;
end
else begin
if (y+1=n) then next(x,y+1);
if (x+1=m) then next(x+1,y);
end;
end;
begin
num:=0;
next(1,1);
writeln(num);
end.
代码如下：
#includestdio.h
unsigned long long dp[21][21]={0};
int main(void){
int n,m;
scanf("%d%d",n,m);
int mx,my;
scanf("%d%d",mx,my);
dp[0][0]=1;
for(int i=0;i=n;i++){
for(int j=0;j=m;j++)
if(i==mxj==my||i==mx-1j==my-2||i==mx-2j==my-1||i==mx-2j==my+1||i==mx-1j==my+2||i==mx+1j==my-2||i==mx+2j==my-1||i==mx+2j==my+1||i==mx+1j==my+2)
dp[i][j]=0;
else if(i==0j!=0)
dp[i][j]=dp[i][j-1];
else if(j==0i!=0)
dp[i][j]=dp[i-1][j];
else if(i==0j==0)
dp[i][j]=1;
else
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
printf("%lld",dp[n][m]);
return 0;
}
//CrossRiverQuestion.java
import java.util.ArrayList;
import java.util.List;
public class CrossRiverQuestion {
public static void main(String[] args) {
CrossRiverQuestion q = new CrossRiverQuestion(5, 4);
q.solveQuestion();
}
private int peoNum;
private int savageNum;
private ListNode resultList = new ArrayListNode();
public ListNode solveQuestion() {
Node n = new Node(peoNum,savageNum,0,0,0,new ArrayListInteger(),0,0);
boolean dfsResult = dfs(n);
if(dfsResult) {
resultList.add(0,n);
for(Node node : resultList) {
System.out.println("左岸传教士："+node.getLeftPeo()+"左岸野人： "+node.getLeftSavage()+" 右岸传教士： "+node.getRightPeo()+"右岸野人："+node.getRightSavage()+"船上传教士："+node.getOnBoatPeoNum()+"船上野人："+node.getOnBoatSavageNum());
}
return resultList;
}
return null;
}
public CrossRiverQuestion(int peoNum, int savageNum) {
super();
this.peoNum = peoNum;
this.savageNum = savageNum;
}
private boolean dfs(Node n) {
if(n.hasVisited()) return false;
n.addCheckSum();
if(n.getLeftPeo()==0n.getLeftSavage()==0) return true;
if(n.getLeftPeo()0||n.getRightPeo()0||n.getLeftSavage()0||n.getRightSavage()0) {
return false;
}
if(n.getLeftPeo()n.getLeftSavage()n.getLeftPeo()0) return false;
if(n.getRightPeo()n.getRightSavage()n.getRightPeo()0) return false;
if(n.getCURR_STATE()==n.getStateBoatLeft()) {
Node n1 = new Node(n.getLeftPeo()-1,n.getLeftSavage()-1,n.getRightPeo()+1,n.getRightSavage()+1,n.getStateBoatRight(),n.getNodesCheckSum(),1,1);
if(dfs(n1)) {
resultList.add(0,n1);
return true;
}
Node n4 = new Node(n.getLeftPeo()-2,n.getLeftSavage(),n.getRightPeo()+2,n.getRightSavage(),n.getStateBoatRight(),n.getNodesCheckSum(),2,0);
if(dfs(n4)) {
resultList.add(0,n4);
return true;
}
Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()-2,n.getRightPeo(),n.getRightSavage()+2,n.getStateBoatRight(),n.getNodesCheckSum(),0,2);
if(dfs(n5)) {
resultList.add(0,n5);
return true;
}
}
else {
Node n6 = new Node(n.getLeftPeo(),n.getLeftSavage()+1,n.getRightPeo(),n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),0,1);
if(dfs(n6)) {
resultList.add(0,n6);
return true;
}
Node n7 = new Node(n.getLeftPeo()+1,n.getLeftSavage(),n.getRightPeo()-1,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),1,0);
if(dfs(n7)) {
resultList.add(0,n7);
return true;
}
Node n1 = new Node(n.getLeftPeo()+1,n.getLeftSavage()+1,n.getRightPeo()-1,n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),1,1);
if(dfs(n1)) {
resultList.add(0,n1);
return true;
}
Node n4 = new Node(n.getLeftPeo()+2,n.getLeftSavage(),n.getRightPeo()-2,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),2,0);
if(dfs(n4)) {
resultList.add(0,n4);
return true;
}
Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()+2,n.getRightPeo(),n.getRightSavage()-2,n.getStateBoatLeft(),n.getNodesCheckSum(),0,2);
if(dfs(n5)) {
resultList.add(0,n5);
return true;
}
}
return false;
}
public ListNode getResultList() {
return resultList;
}
}
Node.java
import java.util.ArrayList;
import java.util.List;
public class Node {
private ListInteger nodesCheckSum = new ArrayListInteger();
private int leftPeo;
private int rightPeo;
private int leftSavage;
private int rightSavage;
private int CURR_STATE = 0;
private int onBoatPeoNum = 0;
private int onBoatSavageNum = 0;
private final int STATE_BOAT_LEFT = 0;
private final int STATE_BOAT_RIGHT = 1;
public Node(int leftPeo, int leftSavage, int rightPeo, int rightSavage, int state, List checkSumList, int onBoatPeoNum, int onBoatSavageNum) {
this.CURR_STATE = state;
this.leftPeo = leftPeo;
this.leftSavage = leftSavage;
this.rightPeo = rightPeo;
this.rightSavage = rightSavage;
this.nodesCheckSum.addAll(checkSumList);
this.onBoatPeoNum = onBoatPeoNum;
this.onBoatSavageNum = onBoatSavageNum;
}
public int getLeftPeo() {
return leftPeo;
}
public void setLeftPeo(int leftPeo) {
this.leftPeo = leftPeo;
}
public int getRightPeo() {
return rightPeo;
}
public void setRightPeo(int rightPeo) {
this.rightPeo = rightPeo;
}
public int getLeftSavage() {
return leftSavage;
}
public void setLeftSavage(int leftSavage) {
this.leftSavage = leftSavage;
}
public int getRightSavage() {
return rightSavage;
}
public void setRightSavage(int rightSavage) {
this.rightSavage = rightSavage;
}
@Override
public String toString() {
return leftPeo+","+leftSavage+","+rightPeo+","+rightSavage+","+CURR_STATE;
}
public int getCURR_STATE() {
return CURR_STATE;
}
public void setCURR_STATE(int cURR_STATE) {
CURR_STATE = cURR_STATE;
}
public int getStateBoatLeft() {
return STATE_BOAT_LEFT;
}
public int getStateBoatRight() {
return STATE_BOAT_RIGHT;
}
public int calcCheckSum() {
return 1*getCURR_STATE()+10*getLeftPeo()+100*getLeftSavage()+1000*getRightPeo()+10000*getRightSavage();
}
public void addCheckSum() {
int checkSum = calcCheckSum();
nodesCheckSum.add(checkSum);
}
public boolean hasVisited() {
int sum = calcCheckSum();
for (Integer checkSum : nodesCheckSum) {
if(checkSum==sum) return true;
}
return false;
}
public ListInteger getNodesCheckSum() {
return nodesCheckSum;
}
public int getOnBoatPeoNum() {
return onBoatPeoNum;
}
public void setOnBoatPeoNum(int onBoatPeoNum) {
this.onBoatPeoNum = onBoatPeoNum;
}
public int getOnBoatSavageNum() {
return onBoatSavageNum;
}
public void setOnBoatSavageNum(int onBoatSavageNum) {
this.onBoatSavageNum = onBoatSavageNum;
}
}
开三个线程，一个代表狼，一个代表羊，一个代表白菜。
一艘船。两个位置。
河有两边，
狼跟羊互斥，羊跟白菜互斥。
即他们不能在船不在此岸边的时候同时存在。
狼，羊，白菜的线程去抢船的位置。（船在此岸）（2个位置，去抢吧，抢到了就占个座。。。。）
再开一个线程。。。。OYE~
船判断能不能离岸，不能离就泄空。能就到对岸就把这两个位置上的泄到对岸，船也到对岸。
然后狼，羊，白菜的线程继续去抢船的位置。
船线程继续判能不能离岸。（船上的位置剩余0或1或2时只要2岸不出现互斥，都可以离岸）
能就走，不能就泄空。。。。
如此往复
直到有一天。。。3个都到对岸了。。OK了。。。
谁会要求写出这样没有逻辑的纯靠运气的程序啊。。。
现在的学校真操蛋。。。。
