读取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;
}
}
}
}
一旦走进死胡头就没法继续了
同时我也想用递归的方法来解决但不知道怎么下手，求各位指点。
$ 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!
建议采样压栈方式比较好！
是求最短路径吗？之间是用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