c++馬攔過河卒

#includeiostream

創(chuàng)新互聯公司是一家網站設計公司，集創(chuàng)意、互聯網應用、軟件技術為一體的創(chuàng)意網站建設服務商，主營產品：響應式網站設計、品牌網站建設、成都營銷網站建設。我們專注企業(yè)品牌在網站中的整體樹立，網絡互動的體驗，以及在手機等移動端的優(yōu)質呈現。成都網站建設、網站制作、移動互聯產品、網絡運營、VI設計、云產品.運維為核心業(yè)務。為用戶提供一站式解決方案，我們深知市場的競爭激烈，認真對待每位客戶，為客戶提供賞析悅目的作品，網站的價值服務。

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('路徑太多，請采用更優(yōu)算法');?

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~

船判斷能不能離岸，不能離就泄空。能就到對岸就把這兩個位置上的泄到對岸，船也到對岸。

然后狼，羊，白菜的線程繼續(xù)去搶船的位置。

船線程繼續(xù)判能不能離岸。（船上的位置剩余0或1或2時只要2岸不出現互斥，都可以離岸）

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

如此往復

直到有一天。。。3個都到對岸了。。OK了。。。

誰會要求寫出這樣沒有邏輯的純靠運氣的程序啊。。。

現在的學校真操蛋。。。。

本文題目：過河卒的代碼java,過河卒啥意思
新聞來源：http://chinadenli.net/article25/dsijdci.html

成都網站建設公司_創(chuàng)新互聯，為您提供網站營銷、微信小程序、小程序開發(fā)、動態(tài)網站、網站內鏈、標簽優(yōu)化

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯