// TwoTurnToDest.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <ctime>using namespace std;#define MAP_HORT_COUNT24 //为简便起见使用固定的行数#define ROAD_TRACK_FAST//定义时采用效率最好,不定义时候采用最容易编写代码。void init(int (*pMap)[MAP_HORT_COUNT],int count){srand((unsigned long)time(0));for (int i=0;i!=count;++i){for (int j = 0;j!=MAP_HORT_COUNT;++j){pMap[i][j] = rand()%3 ? 0:1;}}}bool findroad_oneTurn(int (*pMap)[MAP_HORT_COUNT],int count,int srcx,int srcy,int destx,int desty){if (count < 0){cout << "bad count" << endl;return false;}if (srcx < 0 || srcx >MAP_HORT_COUNT-1 || srcy <0 || srcy > count-1 || destx < 0 || destx > MAP_HORT_COUNT-1 || desty < 0 || desty >count-1){cout << "out of range!" << endl;return false;}//cout << "pMap[srcx][srcy]-pMap[destx][desty]"<< pMap[srcx][srcy] << ","<< pMap[destx][desty]<<endl;//确认源点和目的点是否都能站if (pMap[srcx][srcy] == 1 || pMap[destx][desty] == 1){cout << "bad source or dest point"<< pMap[srcx][srcy] << pMap[destx][desty] << endl;return false;}//计算X,Y偏移int offsetx = destx - srcx;int offsety = desty - srcy;if (offsetx == 0 && offsetx == offsety){cout << "source and dest point is same" << endl;return true;}//先横向,再纵向int nowpointx = srcx;int nowpointy = srcy;bool bHFirstValide = true;bool bHFirstHertValide = true;while (nowpointx != destx){if (offsetx < 0)//目的点在开始点左边nowpointx --;//向左移动elsenowpointx ++;//向右移动if (pMap[nowpointx][nowpointy] == 1){bHFirstHertValide = false;break;}}//cout << "bHFirstHertValide = " << bHFirstHertValide << endl;if (bHFirstHertValide)//横向移动能到达目的点{while (nowpointy != desty){if (offsety < 0)nowpointy --;elsenowpointy ++;if (pMap[nowpointx][nowpointy] == 1){bHFirstValide = false;break;}}if (bHFirstValide){//cout << "bHFirstValide = true" << endl;return true;//纵向也能到达位置。}}//cout << "bHFirstValide = false" << endl;//先横线再纵向不能到达目的点,尝试先纵向移动,再横向移动。nowpointx = srcx;nowpointy = srcy;while (nowpointy != desty){if (offsety < 0)nowpointy --;elsenowpointy ++;if (pMap[nowpointx][nowpointy] == 1){return false;//不可到达}}while (nowpointx != destx){if (offsetx < 0)nowpointx --;elsenowpointx ++;if (pMap[nowpointx][nowpointy] == 1){return false;}}return true;}bool findroad_twoTurn(int (*pMap)[MAP_HORT_COUNT],int count,int srcx,int srcy,int destx,int desty){if (count < 0){cout << "bad count" << endl;return false;}if (srcx < 0 || srcx >MAP_HORT_COUNT-1 || srcy <0 || srcy > count-1 || destx < 0 || destx > MAP_HORT_COUNT-1 || desty < 0 || desty >count-1){cout << "out of range!" << endl;return false;}//cout << "pMap[srcx][srcy]-pMap[destx][desty]"<< pMap[srcx][srcy] << ","<< pMap[destx][desty]<<endl;//确认源点和目的点是否都能站if (pMap[srcx][srcy] == 1 || pMap[destx][desty] == 1){cout << "bad source or dest point"<< pMap[srcx][srcy] << pMap[destx][desty] << endl;return false;}if (findroad_oneTurn(pMap,count,srcx,srcy,destx,desty))//利用之前先的算法,先判断能否一次到达。{return true;}//第一种方法比较取巧,对起始点先向终点方向的X方向横向走,对于路途的每个点调用一次findroad_oneTurn看该点再转一个弯能否到达//如先横向的方法无效,则换成先朝终点方向的Y方向纵向走,对于路途每个点调用一次findroad_oneTurn.//但是该方法的效率要比第二种的方法差一半。这是因为在findroad_oneTurn中是同时判断两种走法(横-纵或者纵-横),而如先确定走横向时,findroad_oneTurn的横纵的走法就多余了。//如不能到达,这按照横向-纵向-横向或者纵向-横向-纵向的方式查找线路//对于横向-纵向-横向的方法,需要查找查找一条纵向的线,该线的终点Y和起点Y分别等于目的点的Y和起始点的Y,然后分别连接两头到起点和终点。//对于纵向-横向-纵向的方法与上类似,只是需要查找一条横向的点。int iOffsetX = destx - srcx;int iOffsetY = desty - srcy;int iPosCurX = srcx;int iPosCurY = srcy;#ifndef ROAD_TRACK_FAST//第一种while (iPosCurX != destx)//先尝试横向走{iOffsetX < 0 ? iPosCurX --:iPosCurX ++;if (findroad_oneTurn(pMap,count,iPosCurX,iPosCurY,destx,desty))return true;}int iPosCurX = srcx;while (iPosCurY != desty){iOffsetY < 0 ? iPosCurY --:iPosCurY ++;if (findroad_oneTurn(pMap,count,iPosCurX,iPosCurY,destx,desty))return true;//再尝试纵向走}#else//1横纵横while (iPosCurX != destx){iOffsetX < 0 ? iPosCurX --:iPosCurX ++;if (pMap[iPosCurX][iPosCurY]){break;//该点不可用,该横向策略失败。}int iPosYTempCur = iPosCurY;bool bLineOk = true;while (iPosYTempCur != desty)//查找纵向可用的线 该纵向的线上的点都可用否?{iOffsetY < 0 ? iPosYTempCur --:iPosYTempCur++;if (pMap[iPosCurX][iPosYTempCur]){bLineOk = false;break;}}if (bLineOk)//如该纵向上的点都可用{int iPosXTempCur = iPosCurX;bool bLastHlineOK = true;while (iPosXTempCur != destx) //最后一段横线上的点都可用否?{iOffsetX < 0 ? iPosXTempCur -- : iPosXTempCur++;if(pMap[iPosXTempCur][iPosCurY]){bLastHlineOK = false;break;}}if(bLastHlineOK)//如最后一段也可用,则返回true.return true;}}//2 纵横纵iPosCurX = srcx;iPosCurY = srcy;while (iPosCurY != desty){iOffsetY < 0 ? iPosCurY --: iPosCurY ++;if (pMap[iPosCurX][iPosCurY]){break;//该点不可用,该纵向策略失败。}int iPosXTempCur = iPosCurX;bool bLineOk = true;while (iPosXTempCur != destx)//查找横向可用的线 该线上的点都可用否?{iOffsetX < 0 ? iPosXTempCur --:iPosXTempCur++;if (pMap[iPosXTempCur][iPosCurY]){bLineOk = false;break;}}if (bLineOk)//如该横向上的点都可用{int iPosYTempCur = iPosCurY;bool bLastlineOK = true;while (iPosYTempCur != desty) //最后一段纵线上的点都可用否?{iOffsetY < 0 ? iPosYTempCur -- : iPosYTempCur++;if(pMap[iPosCurX][iPosYTempCur]){bLastlineOK = false;break;}}if(bLastlineOK)//如最后一段也可用,则返回true.return true;}}#endifreturn false;}int _tmain(int argc, _TCHAR* argv[]){int Map[24][MAP_HORT_COUNT];init(Map,24);cout << "map is :" << endl;for (int j=0;j!=MAP_HORT_COUNT;++j){//cout << j <<"Column "; for (int i=0;i!=24;++i){cout << Map[i][j] << ' ';}cout << endl;}cout << endl;cout << "enter the positon.1 1 2 2 means (1,1),(2,2)" << endl;int ibeginx,ibeginy,iendx,iendy;cin >> ibeginx >> ibeginy >> iendx >> iendy;cout << "find ("<< ibeginx <<","<<ibeginy<<"),(" << iendx << "," << iendy <<"):" << endl;bool bFind = findroad_twoTurn(Map,24,ibeginx,ibeginy,iendx,iendy);cout << (bFind?"Road is Available":"Road is not Available") << endl;return 0;}// TwoTurnToDest.cpp : 定义控制台应用程序的入口点。//#include 你的当前访问异常,请进行认证后继续阅读剩余内容。 提交