【机试练习】【C++】【Codeup 5978】【递归入门】走迷宫

#include<cstdio> #include<vector> #include<cstring> // http://codeup.cn/problem.php?cid=100000608&pid=5 using namespace std; struct Point{ int x = -1; int y = -1; }; vector<Point> history; int colnum = -1, rownum = -1; int maze[30][30] = {0}; // 大二维数组的定义 bool now_walked[30][30] = {false}; bool have_road = false; // 这是增量数组 int X[4] = {0, -1, 0, 1}; int Y[4] = {-1, 0, 1, 0}; // 这里注意，增量数组的取值并不随意，来源于题目中的要求 // 全局的起点和终点 Point startp, endp; // 查询该点是否能站立 bool can_stand(int x, int y){ if(x < 1 || y < 1 || x > rownum || y > colnum){ return false; } if(maze[x][y] != 1 || now_walked[x][y] == true){ return false; } return true; } void dfs(Point p){ if(p.x == endp.x && p.y == endp.y){ for(vector<Point>::iterator it = history.begin(); it != history.end(); it++){ if(it + 1 == history.end()){ printf("(%d,%d)\n", it -> x, it -> y); } else printf("(%d,%d)->", it -> x, it -> y); } have_road = true; return; } for(int i = 0; i < 4; i++){ Point g; g.x = p.x + X[i]; g.y = p.y + Y[i]; if(can_stand(g.x, g.y)){ // 将进栈，打标和出栈，去标的动作与递归分离出来，才能支持if中的return history.push_back(g); now_walked[g.x][g.y] = true; dfs(g); history.pop_back(); now_walked[g.x][g.y] = false; } } } int main(){ //freopen("1.txt", "r", stdin); scanf("%d %d", &rownum, &colnum); for(int i = 1; i <= rownum; i ++){ for(int j = 1; j <= colnum; j++){ scanf("%d", &(maze[i][j])); } } scanf("%d %d", &startp.x, &startp.y); scanf("%d %d", &endp.x, &endp.y); history.push_back(startp); now_walked[startp.x][startp.y] = true; dfs(startp); history.pop_back(); now_walked[startp.x][startp.y] = false; if(!have_road){ printf("-1\n"); } return 0; }