c++马拦过河卒

#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;

}

急！Pascal编程：过河卒（无马拦）

递归算法，适合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.

求助！C++过河卒问题。

代码如下：

#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;

}

用java实现野人传教士过河问题

//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;

}

}

如何用Java编写三个线程实现狼羊白菜过河问题

开三个线程，一个代表狼，一个代表羊，一个代表白菜。

一艘船。两个位置。

河有两边，

狼跟羊互斥，羊跟白菜互斥。

即他们不能在船不在此岸边的时候同时存在。

狼，羊，白菜的线程去抢船的位置。（船在此岸）（2个位置，去抢吧，抢到了就占个座。。。。）

再开一个线程。。。。OYE~

船判断能不能离岸，不能离就泄空。能就到对岸就把这两个位置上的泄到对岸，船也到对岸。

然后狼，羊，白菜的线程继续去抢船的位置。

船线程继续判能不能离岸。（船上的位置剩余0或1或2时只要2岸不出现互斥，都可以离岸）

能就走，不能就泄空。。。。

如此往复

直到有一天。。。3个都到对岸了。。OK了。。。

谁会要求写出这样没有逻辑的纯靠运气的程序啊。。。

现在的学校真操蛋。。。。

分享名称：过河卒的代码java,过河卒啥意思
当前URL：http://pwwzsj.com/article/dsijdci.html