Board logo

標題: 已解決 [打印本頁]
作者: jy02453563    時間: 2008-11-7 14:22     標題: 已解決

本帖最後由 jy02453563 於 2010-6-23 14:08 編輯

thx~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
作者: freewave    時間: 2008-11-7 14:36

nextstep函数是判断当前所处位置（x，y）是否可以向前（返回1）、向左（返回2）、向右（返回3）、向后（返回4）
作者: jy02453563    時間: 2008-11-7 17:16

原帖由 freewave 於 2008-11-7 14:36 發表
nextstep函数是判断当前所处位置（x，y）是否可以向前（返回1）、向左（返回2）、向右（返回3）、向后（返回4）

我知道~但是我不知道讓怎麼改
  1.     if(input[x+1][y]=='.'){
  2.     d=1;}
  3.     if(input[x][y+1]=='.'){
  4.     d=2;}
  5.     if(input[x][y-1]=='.'){
  6.     d=3;}
  7.     if(input[x-1][y]=='.'){
  8.     d=4;}
複製代碼
是我自己加進去~但是跑不出來,不懂改><~用else if也不行...想不出來...
作者: Newbie    時間: 2008-11-7 17:39

原帖由 jy02453563 於 2008-11-7 17:16 發表

我知道~但是我不知道讓怎麼改    if(input[x+1][y]=='.'){
    d=1;}
    if(input[x][y+1]=='.'){
    d=2;}
    if(input[x][y-1]=='.'){
    d=3;}
    if(input[x-1][y]=='.'){
    d=4;}是我自己加進去~但是跑不出來,不懂改>

第一步會行落第二層, 但第二步會上返去, 係nextstep內d先會等如2, 然後等如3, 最後等如4, 再轉回主程式, 會回到上層, 然後不斷重復.... (好似係)
作者: freewave    時間: 2008-11-7 17:50

要搜索迷宫有没有出路， 就要遍历所有的路径， 直到有一条能够走出去， 可以通过递归来做。

ps：你的nextstep函数，只是判断从当前位置可以向哪里走， 因为你设定了run<3000， 所以不一定能够走出去的。

我要外出， 如有需要周六可以给你提供个例子。
作者: jy02453563    時間: 2008-11-9 16:11

求救.......................
作者: freewave    時間: 2008-11-9 21:41

  1. #include "stdafx.h"
  2. #include <assert.h>
  3. #include <vector>
  4. #include<iostream.h>
  5. #include<fstream.h>

  7. #pragma warning(disable:4786)
  8. /*
  9.   # 16 * 16 的迷宫, '.'表示可以行走， '*'不可以行走
  10.   (0,0)
  11.   |---------------------->(x direction)
  12.   |*.**************
  13.   |*........*******
  14.   |*.******.*******
  15.   |*...***..*******
  16.   |****.**.*.....**
  17.   |**...**.*.***.**
  18.   |**.***....***.**
  19.   |**..*..**.***.**
  20.   |***.*.*...***.**
  21.   |**..*.**.****.**
  22.   |**....**......**
  23.   |**.*.*****.*****
  24.   |*..*.*...*.*****
  25.   |*.**...*.*.*****
  26.   |*.******.*.*****
  27.   |********.*******
  28.   |
  29.   (y direction)
  30. */


  33. enum Direction
  34. {
  35.         FORE = 0x00000001,
  36.         BACK = 0x00000002,
  37.         LEFT = 0x00000004,
  38.         RIGHT = 0x00000008
  39. };

  41. typedef struct tagPoint
  42. {
  43.         int row, column;
  44.         tagPoint ()
  45.         {
  46.                 row = 0;
  47.                 column = 0;
  48.         }

  50.         tagPoint(int row, int column)
  51.         {
  52.                 this->row = row;
  53.                 this->column = column;
  54.         }
  55. } Point;

  57. typedef struct tagMatrixPos : public tagPoint
  58. {
  59.         int wayDirections, wayDirectionsMarked;

  61.         tagMatrixPos()
  62.         {
  63.                 wayDirections = 0;
  64.                 wayDirectionsMarked = 0;
  65.         }
  66. } MatrixPos;


  69. //该类代表一个迷宫
  70. class Matrix
  71. {
  72. private:
  73.         int rows, columns;
  74.         int directions[4];
  75.         MatrixPos *pEndPos;
  76.         MatrixPos *pEntrance;
  77.         std::vector< std::vector<MatrixPos *> > matrixArray;
  78.         std::vector< std::vector<char> > matrixMaps;
  79.         std::vector<Point> ways;
  80. protected:
  81.         MatrixPos * GetFirstPos()
  82.         {
  83.                 return pEntrance;
  84.         }

  86.         //判断currentPos节点某个方向是否存在邻居节点
  87.         bool HasNextPos(Direction direction, MatrixPos *currentPos)
  88.         {
  89.                 if (currentPos == NULL)        
  90.                         return false;
  91.                
  92.                 switch (direction)
  93.                 {
  94.                 case FORE:
  95.                         return currentPos->row < rows - 1;
  96.                 case LEFT:
  97.                         return currentPos->column < columns - 1;
  98.                 case RIGHT:
  99.                         return currentPos->column > 0;
  100.                 case BACK:
  101.                         return currentPos->row > 0;
  102.                 }
  103.         }
  104.         
  105.         //获取currentPos某个方向的邻居节点
  106.         MatrixPos *GetPos(Direction direction, MatrixPos *currentPos)
  107.         {
  108.                 if (!HasNextPos(direction, currentPos))
  109.                         return NULL;
  110.                
  111.                 switch (direction)
  112.                 {
  113.                 case FORE:
  114.                         return matrixArray[currentPos->row + 1][currentPos->column];
  115.                 case LEFT:
  116.                         return matrixArray[currentPos->row][currentPos->column + 1];
  117.                 case RIGHT:
  118.                         return matrixArray[currentPos->row][currentPos->column - 1];
  119.                 case BACK:
  120.                         return currentPos->row == 0 ? NULL : matrixArray[currentPos->row - 1][currentPos->column];
  121.                 }
  122.         }
  123.         
  124.         void SetPosition(Direction direction, MatrixPos *pos)
  125.         {
  126.                 pos->wayDirections = pos->wayDirections | (int)direction;
  127.         }

  129.         //标记节点的某个方向已经走过
  130.         void MarkPosition(Direction direction, MatrixPos *pos)
  131.         {
  132.                 pos->wayDirectionsMarked = pos->wayDirectionsMarked | (int)direction;
  133.         }
  134.         
  135.         //测试节点的某个方向是否可以通过
  136.         bool TestDirection(Direction direction, MatrixPos *pos)
  137.         {
  138.                 if ((pos->wayDirections & direction) != direction)
  139.                         return false;
  140.                
  141.                 return (pos->wayDirectionsMarked & direction) != direction;
  142.         }


  145.         //从某个节点开始寻径
  146.         bool WalkFromPos(MatrixPos *pos)
  147.         {
  148.                 bool hasWay = false;
  149.                 if (pos == NULL)
  150.                         return false;

  152.                 //到达y方向的边界则结束
  153.                 if (pos->row == rows - 1) {
  154.                         pEndPos = pos;
  155.                         return true;
  156.                 }

  158.                 //从当前点向前、左、右、后依次测试
  159.                 for (int i = 0; i < 4; i++) {
  160.                         if (TestDirection((Direction)directions[i], pos)) {
  161.                                 MatrixPos *pNextPos = GetPos((Direction)directions[i], pos);
  162.                                 MarkPosition((Direction)directions[i], pos);
  163.                                 if (WalkFromPos(pNextPos)) {
  164.                                         hasWay = true;
  165.                                         ways.push_back(Point(pNextPos->row, pNextPos->column));
  166.                                 }
  167.                         }
  168.                 }

  170.                 return hasWay;
  171.         }
  172. public:
  173.         Matrix()
  174.         {
  175.                 pEntrance = NULL;
  176.                 pEndPos = NULL;
  177.                 rows = columns = 0;

  179.                 directions[0] = FORE;
  180.                 directions[1] = LEFT;
  181.                 directions[2] = RIGHT;
  182.                 directions[3] = BACK;
  183.         }

  185.         ~Matrix()
  186.         {
  187.                 for (int i = 0; i < matrixArray.size(); i++) {
  188.                         for (int j = 0; j < matrixArray.size(); j++)
  189.                                 delete matrixArray[i][j];
  190.                 }

  192.                 matrixArray.clear();
  193.         }

  195.         bool ReadMatrix(const char* pszFile, int rows, int columns)
  196.         {
  197.                 char pos;
  198.                 MatrixPos *pCurrent = NULL;
  199.                 MatrixPos *pRight = NULL;
  200.                 MatrixPos *pPrev = NULL;

  202.                 ifstream fin(pszFile);
  203.                 if (!fin.is_open())
  204.                         return false;

  206.                 this->rows = rows;
  207.                 this->columns = columns;
  208.                 for (int i = 0; i < rows; i++) {
  209.                         matrixArray.push_back(std::vector<MatrixPos *>());
  210.                         matrixMaps.push_back(std::vector<char>());
  211.                         for (int j = 0; j < columns; j++) {
  212.                                 fin >> pos;

  214.                                 pCurrent = new MatrixPos();
  215.                                 pCurrent->row = i;
  216.                                 pCurrent->column = j;
  217.                                 matrixArray[i].push_back(pCurrent);
  218.                                 matrixMaps[i].push_back(pos);

  220.                                 pRight = GetPos(RIGHT, pCurrent);
  221.                                 pPrev = GetPos(BACK, pCurrent);
  222.                                 //设置其左、后节点的路径
  223.                                 if (pos == '.') {
  224.                                         if (pRight != NULL)
  225.                                                 SetPosition(LEFT, pRight);

  227.                                         if (pPrev != NULL)
  228.                                                 SetPosition(FORE, pPrev);

  230.                                         if (i == 0)
  231.                                                 pEntrance = pCurrent;
  232.                                 }

  234.                                 if (pRight != NULL && matrixMaps[i][j-1] == '.')
  235.                                         SetPosition(RIGHT, pCurrent);
  236.                                 if (pPrev != NULL && matrixMaps[i-1][j] == '.')
  237.                                         SetPosition(BACK, pCurrent);
  238.                         }
  239.                 }
  240.                
  241.                 fin.close();
  242.                 return true;
  243.         }



  247.         //寻找路径
  248.         bool Walk()
  249.         {
  250.                 MatrixPos *pCurrentPos = GetFirstPos();
  251.                 return WalkFromPos(pCurrentPos);
  252.         }

  254.         //打印路径
  255.         void PrintWay()
  256.         {
  257.                 printf ("[%d,%d] - > ", pEntrance->row + 1, pEntrance->column + 1);
  258.                 for (int i = ways.size() - 1 ; i >= 0 ; i--) {
  259.                         printf ("[%d,%d] -> ", ways[i].row + 1, ways[i].column + 1);
  260.                 }

  262.                 printf ("[%d,%d]", pEndPos->row + 1, pEndPos->column + 1);
  263.         }

  265.         void PrintMatrix()
  266.         {
  267.                 for (int i = 0; i < rows; i++) {
  268.                         cout << endl;
  269.                         for (int j = 0; j < columns; i++) {
  270.                                 cout << matrixMaps[i][j] << endl;
  271.                         }
  272.                 }
  273.         }
  274. };


  277. int main(int argc, char* argv[])
  278. {
  279.         Matrix matrix;
  280.         if (!matrix.ReadMatrix("c:\\mg.txt", 16, 16))
  281.                 printf("read matrix failed");

  283.         if (matrix.Walk())
  284.         {
  285.                 printf("Find a way :\n");
  286.                 matrix.PrintWay();
  287.         }
  288.         else
  289.                 printf("no way found");

  291.         printf("\npress any key to exit");
  292.         getchar();
  293.         return 0;
  294. }
複製代碼
不好意思， 刚发现论坛将[ i ] 转换成斜体了， 所以代码中[ i ] 都没有了。 先已更正

[ 本帖最後由 freewave 於 2008-11-11 21:26 編輯 ]
作者: freewave    時間: 2008-11-9 21:45

周末出去玩了 :)
上面我刚写了个例子， 是利用递归寻找路径，例如上面16*16的迷宫的路径输出如下（这个路径不是最短路径，需要再加以计算才能得到，抱歉我没有做...）：
[row,column]->[row,column]->....->[row,column] 代表各个点之间的走动

[1,2] - > [2,2] -> [3,2] -> [4,2] -> [4,3] -> [4,4] -> [4,3] -> [4,2] -> [3,2] -
> [2,2] -> [2,3] -> [2,4] -> [2,5] -> [2,6] -> [2,7] -> [2,8] -> [2,9] -> [3,9]
-> [4,9] -> [4,8] -> [5,8] -> [6,8] -> [7,8] -> [7,9] -> [7,10] -> [8,10] -> [9,
10] -> [9,9] -> [10,9] -> [11,9] -> [11,10] -> [11,11] -> [12,11] -> [13,11] ->
[14,11] -> [15,11] -> [14,11] -> [13,11] -> [12,11] -> [11,11] -> [11,12] -> [11
,13] -> [11,14] -> [11,13] -> [11,12] -> [11,11] -> [11,10] -> [11,9] -> [10,9]
-> [9,9] -> [9,10] -> [8,10] -> [7,10] -> [7,9] -> [7,8] -> [7,7] -> [8,7] -> [8
,6] -> [9,6] -> [10,6] -> [11,6] -> [11,5] -> [12,5] -> [13,5] -> [14,5] -> [14,
6] -> [14,7] -> [13,7] -> [13,8] -> [13,9] -> [14,9] -> [15,9] -> [16,9]
作者: jy02453563    時間: 2008-11-10 01:28

可以只修改
  1. int nextstep(int x,int y)
  2. {
  3.     char input[37][37];
  4.     int d=0;
  5.     ifstream fin("mg.txt");
  6.     for(int i=0;i<37;i++){
  7.             for(int j=0;j<37;j++){
  8.             fin>>input[i][j];}
  9.     }
  10.     fin.close();
  11.     if(input[x+1][y]=='.'){
  12.     d=1;}
  13.     if(input[x][y+1]=='.'){
  14.     d=2;}
  15.     if(input[x][y-1]=='.'){
  16.     d=3;}
  17.     if(input[x-1][y]=='.'){
  18.     d=4;}
  19.     return d;
  20. }
複製代碼
的內容就能完成嗎?thx><~
作者: freewave    時間: 2008-11-10 21:23

这样实现比较困难， 需要保存尝试过的路径信息，不至于走重复的路线。nextstep里面有回退， 回退后又会走走过的路线， 这样就陷入了死循环。
作者: thinkpanda    時間: 2008-11-11 01:18

我做tutor 教year 1 C++ 既時候, 有個assignment 同呢個幾乎一模一樣....
作者: Tony仔    時間: 2008-11-11 01:22

wiki下: DFS  depth-first search la
作者: jy02453563    時間: 2008-11-11 14:33

只能說我也覺得限制太多...但一定只能改那個位置><~
作者: Newbie    時間: 2008-11-11 16:17

  1. if(input[x+1][y]=='.'){
  2.     d=1; return d; }
  3. if(input[x][y-1]=='.'){
  4.     d=3; return d; }
  5. if(input[x-1][y]=='.'){
  6.     d=4; return d; }
  7. if(input[x][y+1]=='.'){
  8.     d=2; return d; }
複製代碼
試過唔得既.....唔使試!

重有個問題, 你每次 call nextstep 就會開1次個txt file, 係咪唔係咁好呢?

[ 本帖最後由 Newbie 於 2008-11-11 17:26 編輯 ]
作者: jy02453563    時間: 2008-11-11 20:43

這個是被老師限制了只能改那個位置...課堂內容教超快,第六課而已~就跳到這裡~頭上都超多問號....
作者: $$$    時間: 2008-11-11 23:25

個陣係UST 讀
都做過但係LAB 嚟
作者: Newbie    時間: 2008-11-12 14:32

  1. #include<iostream.h>
  2. #include<fstream.h>
  3. int nextstep(int,int, const char output[][37]);
  4. int main(void)
  5. {
  6. int cpx=0,cpy=18,dd,run=0;
  7. char input[37][37],trace[37][37];
  8. char ttt;
  9. cout<<"0123456789012345678901234567890123456\n";
  10. ifstream fin("mg.txt");
  11. for(int i=0;i<37;i++){
  12.          for(int j=0;j<37;j++){
  13.          fin>>input[i][j];
  14.          trace[i][j]=input[i][j];
  15.          cout<<input[i][j];}
  16. cout<<i<<"\n";}
  17. fin.close();

  19. trace[0][18]='o';
  20. while(cpx!=36 && run<3000)
  21. {
  22.   dd=nextstep(cpx,cpy,input);
  23.   if(dd==1 && input[cpx+1][cpy]=='.')
  24.       {cpx++;run++;trace[cpx][cpy]='o';}
  25.   else if(dd==2 && input[cpx][cpy+1]=='.')
  26.       {cpy++;run++;trace[cpx][cpy]='o';}
  27.   else if(dd==3 && input[cpx][cpy-1]=='.')
  28.       {cpy--;run++;trace[cpx][cpy]='o';}
  29.   else if(dd==4 && input[cpx-1][cpy]=='.')
  30.       {cpx--;run++;trace[cpx][cpy]='o';}
  31.   else
  32.       {run=10000000;cout<<"cpx="<<cpx<<",cpy="<<cpy<<",dd="<<dd<<"\n";}
  33. // system("PAUSE");

  35.   cout<<run<<"  "<<"cpx="<<cpx<<",cpy="<<cpy<<",dd="<<dd<<"\n";
  36. }

  38.   if(cpx==36)   {cout<<"到達終點 cpx="<<cpx<<",cpy="<<cpy<<"\n"; }

  40.   cout<<"0123456789012345678901234567890123456\n";
  41.   for(int i=0;i<37;i++)
  42.   {   for(int j=0;j<37;j++)
  43.       {  cout<<trace[i][j];
  44.         }
  45.       cout<<i<<"\n";
  46.   }
  47. system("PAUSE");
  48. }

  50. int nextstep(int x,int y, const char output[][37])
  51. {
  52. /*
  53.     char input[37][37];
  54.     int d=0;
  55.     ifstream fin("mg.txt");
  56.     for(int i=0;i<37;i++){
  57.             for(int j=0;j<37;j++){
  58.             fin>>input[i][j];}
  59.     }
  60.     fin.close();
  61. */
  62.     static int d_Last = 0;
  63.     int d=0;
  64. //    cout<<"Last direction = "<<d_Last<<"\n";
  65. //      1, 先定上一步行既方向
  66. //      2, check 右邊有冇路行, 有就轉去右邊及更新 d_Last
  67. //      3, 如右邊冇路, check 前方有冇路行, 有就向前行, 更新 d_Last
  68. //      4, 如前路冇路行, check 左邊有冇路行, 有就向左邊行, 更新 d_Last
  69. //      5, 如左邊都冇路行(即係死巷), 就轉頭向後行及更新 d_Last
  70. //
  71.     switch (d_Last)
  72.     {
  73.         case 0:
  74.         case 1:     //如果先前向下
  75.             if (output[x][y-1]=='.') { d=3; }
  76.             else if(output[x+1][y]=='.') { d=1; }
  77.             else if(output[x][y+1]=='.') { d=2; }
  78.             else if(output[x-1][y]=='.') { d=4; }
  79.             //print error...if no match
  80.             break;
  81.         case 3:     //如果先前向左
  82.             if (output[x-1][y]=='.') { d=4; }
  83.             else if(output[x][y-1]=='.') { d=3; }
  84.             else if(output[x+1][y]=='.') { d=1; }
  85.             else if(output[x][y+1]=='.') { d=2; }
  86.             //print error...if no match
  87.             break;
  88.         case 4:     //如果先前向上
  89.             if (output[x][y+1]=='.') { d=2; }
  90.             else if(output[x-1][y]=='.') { d=4; }
  91.             else if(output[x][y-1]=='.') { d=3; }
  92.             else if(output[x+1][y]=='.') { d=1; }
  93.             //print error...if no match
  94.             break;
  95.         case 2:     //如果先前向右
  96.             if (output[x+1][y]=='.') { d=1; }
  97.             else if(output[x][y+1]=='.') { d=2; }
  98.             else if(output[x-1][y]=='.') { d=4; }
  99.             else if(output[x][y-1]=='.') { d=3; }
  100.             //print error...if no match
  101.             break;
  102.         default:
  103.             //print error
  104.             break;
  105.         }
  106.         d_Last=d;       //更新 d_Last
  107.         return d;
  108. }

  110. //    if(output[x+1][y]=='.'){
  111. //    d=1; return d; }
  112. //    if(output[x][y-1]=='.'){
  113. //    d=3; return d; }
  114. //    if(output[x-1][y]=='.'){
  115. //    d=4; return d; }
  116. //    if(output[x][y+1]=='.'){
  117. //    d=2; return d; }
  118. //    return d;
  119. //}
複製代碼
雖然蠢d, 但都好似行到出去....

[ 本帖最後由 Newbie 於 2008-11-12 14:44 編輯 ]
作者: Gundamdriver    時間: 2008-11-12 15:50

同今年IVE HDSE Year 2個Assignment好似... 不過我地用Java寫。
作者: jy02453563    時間: 2008-11-12 23:11

原帖由 Newbie 於 2008-11-12 14:32 發表
#include
#include
int nextstep(int,int, const char output[][37]);
int main(void)
{
int cpx=0,cpy=18,dd,run=0;
char input[37][37],trace[37][37];
char ttt;
cout

先謝謝你~因為我們功課不能修改主程式部份~只能改nextstep~所以不能用
不過我明白你寫的內容的意思~我再自己修改一下吧~thx




歡迎光臨 電腦領域 HKEPC Hardware (https://www.hkepc.com/forum/) Powered by Discuz! 7.2