C++中简单的寻路问题,求指点

读取txt中的迷宫,并读取起始点坐标和目标点坐标进行寻路,这是我的代码:
#include

#include <fstream>

#include <sstream>


using namespace std;


struct Move

{

    int x;
      int y;

}Move[1000];


int Maze(string name,int sx,int sy,int gx,int gy);


int main(int nargs, char *argv[])

{

  string name = argv[1];
    int sx = stoul(string(argv[2]));

  int sy = stoul(string(argv[3]));

  int gx = stoul(string(argv[4]));

  int gy = stoul(string(argv[5]));


  Maze(name,sx,sy,gx,gy);   


  cout<<endl;

}


int Maze(string name,int sx,int sy,int gx,int gy)

{   


  ifstream read(name);

  int a[2]; 


//read the size of the maze and create an array to store it 

  for(int i=0;i<2;i++)

  {

    read>>a[i];

  }


  int row = a[0];

  int col = a[1];

  int maze[row][col];


  for(int i=0;i<row;i++)

  { 

    for(int j=0;j<col;j++)

  {   

    read>>maze[i][j];

   }

  }  

/*for(int i=0;i<row;i++)

{

for(int j=0;j<col;j++)

{

cout<<map[i][j]<<" ";

}

cout<<endl;

}*/

read.close();


if(maze[sx][sy]==1||maze[gx][gy]==1)

{

  cout<<"Error place!"<<endl;

}


  else if(maze[sx+1][sy]==1&&maze[sx][sy+1]==1&&maze[sx-1][sy]==1&&maze[sx][sy-1]==1)

{

  cout<<"No paths to go!"<<endl;

}


  else

{

  Move[0].x = sx;

  Move[0].y = sy;

  int i = 1;

  while(Move[0].x!=gx && Move[0].y!=gy)

{


if(maze[sx+1][sy]==0)

{

Move[0].x = Move[0].x+1;

cout<<"D"<<" ";

continue;               

}


else if(maze[sx-1][sy]==0)

{

Move[0].x = Move[0].x-1;

cout<<"U"<<" "; 

continue;           

}


else if(maze[sx][sy+1]==0)

{

Move[0].y = Move[0].y+1;

cout<<"R"<<" ";     

continue;       

}


else if(maze[sx][sy-1]==0)

{

Move[0].y = Move[0].y-1;

cout<<"L"<<" "; 

continue;           

   }

 }

}

}
一旦走进死胡头就没法继续了
同时我也想用递归的方法来解决但不知道怎么下手,求各位指点。

c++

7个回答

$ cat maze.cpp
#include
#include
#include
#include

using namespace std;

int gx;
int gy;

int *maze;
int rows;
int cols;

#define MAZE(x, y) maze[cols*(x)+(y)]

int initMaze(const char *name, int **maze, int *rows, int *cols)
{

ifstream ifs(name);

ifs >> *rows;
ifs >> *cols;

*maze = new int[*rows * *cols];

for (int i = 0; i < *rows; i++)
{ 
    for (int j = 0; j < *cols; j++)
    {   
        ifs >> (*maze)[*cols*i+j];
    }
}  

if (!ifs)
{
   cout << "Error reading " << name << endl;
   return -1;
}

ifs.close();

return 0;

}

bool checkMaze(int *maze, int rows, int cols, int sx, int sy, int gx, int gy)
{
for (int i = 0; i < rows * cols; i++)
{
cout << maze[i] << " ";
}

cout << endl << endl;

for (int i = 0; i < rows; i++)
{
    for (int j = 0; j < cols; j++)
    {
        cout << MAZE(i, j) << " ";
    }

    cout << endl;
}

if (sx < 0 || sy < 0 || gx < 0 || gy < 0
    || sx >= rows || sy >= cols || gx >= rows || gy >= cols)
{
    cout << "Error (x, y)" << endl;
    return false;
}

if (MAZE(sx, sy) != 0 || MAZE(gx, gy) != 0)
{
    cout << "Error place!" << endl;
    return false;
}

return true;

}

bool walkUp(int x, int y);
bool walkDown(int x, int y);
bool walkLeft(int x, int y);
bool walkRight(int x, int y);

void findExit(int x, int y)
{
cout << "(" << x+1 << ", " << y+1 << ") --> (" << gx+1 << ", " << gy+1 << ")" << endl << endl;

cout << "(" << x+1 << ", " << y+1 << ") ";
if (x == gx && y == gy
    || walkDown(x+1, y)
    || walkUp(x-1, y)
    || walkRight(x, y+1)
    || walkLeft(x, y-1))
{
    cout << endl;
    cout << "Done!" << endl;
    return;
}

cout << endl;
cout << "Lost!" << endl;

}

bool walkUp(int x, int y)
{
if (x < 0) return false;
if (MAZE(x, y) != 0) return false;

cout << "U(" << x+1 << "," << y+1 << ") ";

if (x-1 == gx && y == gy)
{
    cout << "U(" << x << "," << y+1 << ") ";
    return true;
}

if (x == gx && y+1 == gy)
{
    cout << "R(" << x+1 << "," << y+2 << ") ";
    return true;
}

if (x == gx && y-1 == gy)
{
    cout << "L(" << x+1 << "," << y << ") ";
    return true;
}

if (walkUp(x-1, y)
    || walkRight(x, y+1)
    || walkLeft(x, y-1))
{
    return true;
}

cout << "D(" << x+2 << "," << y+1 << ") ";
return false;

}

bool walkDown(int x, int y)
{
if (x >= rows) return false;
if (MAZE(x, y) != 0) return false;

cout << "D(" << x+1 << "," << y+1 << ") ";

if (x+1 == gx && y == gy)
{
    cout << "D(" << x+2 << "," << y+1 << ") ";
    return true;
}

if (x == gx && y+1 == gy)
{
    cout << "R(" << x+1 << "," << y+2 << ") ";
    return true;
}

if (x == gx && y-1 == gy)
{
    cout << "L(" << x+1 << "," << y << ") ";
    return true;
}

if (walkDown(x+1, y)
    || walkRight(x, y+1)
    || walkLeft(x, y-1))
{
    return true;
}

cout << "U(" << x << "," << y+1 << ") ";
return false;

}

bool walkLeft(int x, int y)
{
if (y < 0) return false;
if (MAZE(x, y) != 0) return false;

cout << "L(" << x+1 << "," << y+1 << ") ";

if (x == gx && y-1 == gy)
{
    cout << "L(" << x+1 << "," << y << ") ";
    return true;
}

if (x-1 == gx && y == gy)
{
    cout << "U(" << x << "," << y+1 << ") ";
    return true;
}   

if (x+1 == gx && y == gy)
{
    cout << "D(" << x+2 << "," << y+1 << ") ";
    return true;
}

if (walkLeft(x, y-1)
    || walkUp(x-1, y)
    || walkDown(x+1, y))
{
    return true;
}

cout << "R(" << x+1 << "," << y+2 << ") ";
return false;

}

bool walkRight(int x, int y)
{
if (y >= cols) return false;
if (MAZE(x, y) != 0) return false;

cout << "R(" << x+1 << "," << y+1 << ") ";

if (x == gx && y+1 == gy)
{
    cout << "R(" << x+1 << "," << y+2 << ") ";
    return true;
}

if (x-1 == gx && y == gy)
{
    cout << "U(" << x << "," << y+1 << ") ";
    return true;
}

if (x+1 == gx && y == gy)
{
    cout << "D(" << x+2 << "," << y+1 << ") ";
    return true;
}

if (walkRight(x, y+1)
    || walkUp(x-1, y)
    || walkDown(x+1, y))
{
    return true;
}

cout << "L(" << x+1 << "," << y << ") ";
return false;

}

int main(int argc, char * const argv[])
{
if (argc != 6)
{
cout << "Usage: " << argv[0] << "MazeMapFile entranceX entranceY exitX exitY" << endl;
return 1;
}

int sx = atoi(argv[2]) - 1;
int sy = atoi(argv[3]) - 1;

gx = atoi(argv[4]) - 1;
gy = atoi(argv[5]) - 1;

if (initMaze(argv[1], &maze, &rows, &cols) != 0
    || !checkMaze(maze, rows, cols, sx, sy, gx, gy))
{
    return 2;
}

cout << endl;

findExit(sx, sy);

cout << endl;
return 0;

}

$ cat maze.txt
4 4
1 0 0 1
0 1 0 0
0 0 0 1
1 0 1 0

$ maze maze.txt 1 2 4 2
1 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0

1 0 0 1
0 1 0 0
0 0 0 1
1 0 1 0

(1, 2) --> (4, 2)

(1, 2) R(1,3) D(2,3) D(3,3) L(3,2) D(4,2)
Done!

userchen
userchen 2、main()函数在代码底部
一年多之前 回复
userchen
userchen 回复userchen: 2
一年多之前 回复
userchen
userchen 回复Desol: 1、walk*返回true说明找到出口,返回false为没有找到。walkDown()是向下走,其它类似。这个判断的意思是当前位置是出口吗?分别试探往下、上、右、左走一步能找到出口吗?只要有一个条件满足就找到了迷宫出口。
一年多之前 回复
Desol
Desol 请问 if (x == gx && y == gy || walkDown(x+1, y) || walkUp(x-1, y) || walkRight(x, y+1) || walkLeft(x, y-1))这个条件是用来判断什么的呢? 还有就是我们老师的要求是要在运行的时候读入五个参数,分别是txt文件名,初始点x,y和目标点x,y,请问你写的读入的参数是哪些呢?
一年多之前 回复

建议采样压栈方式比较好!

是求最短路径吗?之间是用java做的,用队列做宽度搜索,一开始创建一个是否被访问的二维数组,把起始坐标放入队列,然后开始用while(对列不为空)进行循环,上下左右开始试探,把访问过的点标为-1,然后1表示墙壁,0表示可行,把可行的点放入队列又重新判断,直到到达终点坐标。

#includ 四个头文件
cstdlib
iostream
fstream
sstream

 public class GameView extends View implements Runnable {  
    /* 声明Paint对象 */  
    private Paint mPaint = null;  

    public GameView(Context context) {  
        super(context);  
        /* 构建对象 */  
        mPaint = new Paint();  

        /* 开启线程 */  
        new Thread(this).start();  
    }  

    public void onDraw(Canvas canvas) {  
        super.onDraw(canvas);  

        /* 设置画布的颜色 */  
        canvas.drawColor(Color.BLACK);  

        /* 设置取消锯齿效果 */  
        mPaint.setAntiAlias(true);  

        /* 设置裁剪区域 */  
        canvas.clipRect(10, 10, 280, 260);  

        /* 线锁定画布 */  
        canvas.save();  
        /* 旋转画布 */  
        canvas.rotate(45.0f);  

        /* 设置颜色及绘制矩形 */  
        mPaint.setColor(Color.RED);  
        canvas.drawRect(new Rect(15, 15, 140, 70), mPaint);  

        /* 解除画布的锁定 */  
        canvas.restore();  

        /* 设置颜色及绘制另一个矩形 */  
        mPaint.setColor(Color.GREEN);  
        canvas.drawRect(new Rect(150, 75, 260, 120), mPaint);  
    }  

    // 触笔事件  
    public boolean onTouchEvent(MotionEvent event) {  
        return true;  
    }  

    // 按键按下事件  
    public boolean onKeyDown(int keyCode, KeyEvent event) {  
        return true;  
    }  

    // 按键弹起事件  
    public boolean onKeyUp(int keyCode, KeyEvent event) {  
        return false;  
    }  

    public boolean onKeyMultiple(int keyCode, int repeatCount, KeyEvent event) {  
        return true;  
    }  

    public void run() {  
        while (!Thread.currentThread().isInterrupted()) {  
            try {  
                Thread.sleep(100);  
            } catch (InterruptedException e) {  
                Thread.currentThread().interrupt();  
            }  
            // 使用postInvalidate可以直接在线程中更新界面  
            postInvalidate();  
        }  
    }  
} 
 Newnode sort(node *q, Newnode *inser)                                
{
    Newnode *temp = q;

    while (1)
    {
        if (temp->next == NULL && temp->nu < inser->nu)     
        {
            temp->next = inser;
            inser->pre = temp;
            return(*q);
        }

        if (temp->pre == NULL && temp->nu > inser->nu)       
        {                                                      
            inser->next = temp;
            temp->pre = inser;  //***

            return(*inser);
        }

        //***
        if (temp->next != NULL)
        {
            temp = temp->next;
            if (temp->nu > inser->nu)
            {
                break;
            }
        }
        //***
    }
    inser->next = temp;
    inser->pre = temp->pre;
    temp->pre->next = inser;
    temp->pre = inser;

    return(*q);
}

Newnode add(Newnode *q)    
{
    int count = 0;
    Newnode qq; //***

    while (1)
    {
        Newnode *newnode;
        newnode = (Newnode *)malloc(sizeof(Newnode));
        scanf("%d,", &newnode->nu);
        if (newnode->nu == -1)
        {
            return(qq); //***
        }
        newnode->next = NULL;
        newnode->pre = NULL;
        scanf("%[^,]%[^\n]", newnode->name, newnode->add);


        if (q->pre == NULL && q->next == NULL && count == 0)
        {
            q = newnode;
            count++;                      
            continue;
        }
        else
            qq = sort(q, newnode);     
    }
    return(qq); //***
}

.Genymotion 6.0 ARM-Translation Genymotion 6.0 的ARM-Tr

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!