Define a 2D array:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
It represents a maze, in which 1 represents the wall, 0 represents the path that can be walked, can only walk horizontally or vertically, can't walk obliquely, and requires programming to find the shortest path from the upper left corner to the lower right corner.
Input
A 5 × 5 two-dimensional array represents a maze. Data guarantees a unique solution.
Output
The shortest path from the upper left corner to the lower right corner, in the format shown in the example.
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
Typical template questions
dfs Code:
#include<string.h> #include<iostream> using namespace std; const int dir[][2] = {1,0,0,1,-1,0,0,-1}; char mp[10][10]; struct node{int x;int y;}; node l[30],m[30]; int minv = 0x3f3f3f3f; int vis[10][10]; void dfs(int x,int y,int cnt) { if(x == 4 && y == 4) { if(cnt < minv) { minv = cnt; for(int i = 0 ; i < cnt ; i++) m[i] = l[i]; } return; } l[cnt].x = x; l[cnt].y = y; for(int i = 0 ; i < 4 ; i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if(nx >= 0 && ny >= 0 && nx < 5 && ny < 5 && mp[nx][ny] == '0' && !vis[nx][ny]) { vis[nx][ny] = 1; dfs(nx,ny,cnt+1); } } } int main(void) { memset(vis,0,sizeof vis); for(int i = 0 ; i < 5 ; i++) for(int j = 0 ; j < 5 ; j++) cin >> mp[i][j]; dfs(0,0,0); for(int i = 0 ; i < minv ; i++) cout << "(" << m[i].x << ", " << m[i].y << ")" << endl; cout << "(4, 4)" << endl; }
bfs Code:
#include<stack> #include<queue> #include<string.h> #include<iostream> using namespace std; const int dir[][2] = {1,0,0,1,-1,0,0,-1}; struct node{int x,y;}; char mp[10][10]; node pro[10][10]; int vis[10][10]; void print() { stack<node>s; node now = pro[5][5]; node next; while(1) { if(now.x == 1 && now.y == 1) break; s.push(now); next = pro[now.x][now.y]; now = next; } while(s.size()) { now = s.top(); s.pop(); cout << "(" << now.x - 1 << ", " << now.y - 1 << ")" << endl; } } void bfs() { queue<node>q; node now,next; now.x = 1; now.y = 1; q.push(now); while(q.size()) { now = q.front(); q.pop(); if(now.x == 5 && now.y == 5) break; for(int i = 0 ; i < 4 ; i++) { next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; if(next.x >= 1 && next.y >= 1 && next.x <= 5 && next.y <= 5 && !vis[next.x][next.y] && mp[next.x][next.y] != '1') { vis[next.x][next.y] = 1; pro[next.x][next.y] = now; q.push(next); } } } } int main(void) { memset(vis,0,sizeof vis); for(int i = 1 ; i <= 5 ; i++) for(int j = 1 ; j <= 5 ; j++) cin >> mp[i][j]; bfs(); cout << "(0, 0)" << endl; print(); cout << "(4, 4)" << endl; return 0; }