problem

Define a two-dimensional array N*M (where 2<=N<=10; 2<=M<=10), as shown under the 5*5 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 labyrinth, in which 1 represents the wall and 0 represents the path that can be taken. It can only walk horizontally or vertically, but not obliquely. It requires programming to find the shortest path from the upper left corner to the lower right corner. The entry point is [0,0], where the first space is the right way to go. Input A two-dimensional array of N * M, representing a maze. The data guarantees that there is only one solution, regardless of the multiple solutions, that is, there is only one channel in the labyrinth. The shortest path from the upper left corner to the lower right corner of Output is in the format shown in the example. Sample Input 0 1 000 1 000 1 00 0 0 0 0 0 1 000 1 1 1 000 1 10 Sample Output (0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (4,4)

Title Solution

(This question does not necessarily use BFS, but it is still used for practice.)

#include"iostream"
#include"vector"
#include"queue"
#include"stack"
using namespace std;

struct node
{
	int x;
	int y;
	int pre;
};
int m, n;
int head = 0; int tail = 1;
node start, EN;

int dis[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };


vector< int > print_path(int tail, node* que)
{
	vector< int > path_track;
	int t = tail;
	while (que[t].pre != -1)
	{
		path_track.insert(path_track.begin(),t);
		t = que[t].pre;
	}
	path_track.insert(path_track.begin(), 0);
	return path_track;
}


int BFS(vector<vector<int>> map, node* que)
{
	node point;
	point = start;
	que[head] = point;
	vector<vector<int>> flag(m, vector<int>(n, 0));
	flag[point.x][point.y] = 1;
	while (head<tail)
	{
		for (int i = 0; i<4; i++)
		{
			int tx = que[head].x + dis[i][0];
			int ty = que[head].y + dis[i][1];
			//cout << flag[0].size() << flag.size();
			//cout << map[tx][ty] << flag[tx][ty];
			if (tx<m && tx >= 0 && ty<n && ty >= 0 && map[tx][ty] == 0)
			if (flag[tx][ty] == 0)
			{
				que[tail].x = tx;
				que[tail].y = ty;
				que[tail].pre = head;
				flag[tx][ty] = 1;
				if (tx == EN.x && ty == EN.y)
				{
					//head is the first step to the end point.
					return tail;
				}
				tail++;
			}
		}
		head++;
	}
	return 0;
}

int main()
{

	while (cin >> m >> n)
	{
	node *que = new node[n*m];
        head = 0; tail = 1;
		start.x = 0; start.y = 0; start.pre = -1;
		EN.x = m - 1; EN.y = n - 1; EN.pre = -1;
		vector<vector<int>> map(m, vector<int>(n, 0));
		for (int i = 0; i<m; i++){
			for (int j = 0; j<n; j++)
			{
				cin >> map[i][j];
			}
		}
		int tail = BFS(map, que);
		vector<int> path_track = print_path(tail, que);
		int ii = path_track[0];
		while (ii<path_track.size())
		{
			cout << "(" << que[path_track[ii]].x << "," << que[path_track[ii]].y << ")" << "\n";
			ii++;
		}
        delete []que;
	}
	return 0;
}

Wrong point

Mistake point super many

1. Define global variables as little as possible. Global variables are intelligently defined as values that are always constant. Others are not defined. Pass parameters are used.
2. Notice that there are multiple case s coming out of the while loop

• When entering multiple case s, special attention should be paid to whether the initialization parameters are initialized before each calculation, and whether there is any initialization in the global variables (it is better not to define the global variables).
• How to enter multiple cases: https://www.nowcoder.com/discussion/276
• Use printf("%lld") for C 64-bit output

int main() {
    int a,b;
    while(scanf("%d %d",&a, &b) != EOF)//Note that while handles multiple case s
        printf("%d\n",a+b);
    return 0;
}

• For C++ 64-bit output, use printf("%lld")

#include <iostream>
using namespace std;
int main() {
    int a,b;
    while(cin >> a >> b)//Note that while handles multiple case s
        cout << a+b << endl;
}

1. Defined new int[n*m] must be valid in N and m, so don't define it as a global variable

2. Array parameter passing, as long as you pass array variables

Backtracking Printing

#include"iostream"
#include"vector"
#include"queue"
#include"stack"
using namespace std;

struct node
{
	int x;
	int y;
	int pre;
};
int m, n;
int head = 0; int tail = 1;
node start, EN;

int dis[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };



// Print and retrospective output of final results
void print_path(int tail, node* que)
{
    if (que[tail].pre != -1)
	    print_path(que[tail].pre, que);
	cout << "(" << que[tail].x << "," << que[tail].y << ")" << "\n";
	return;
}

int BFS(vector<vector<int>> map, node* que)
{
	node point;
	point = start;
	que[head] = point;
	vector<vector<int>> flag(m, vector<int>(n, 0));
	flag[point.x][point.y] = 1;
	while (head<tail)
	{
		for (int i = 0; i<4; i++)
		{
			int tx = que[head].x + dis[i][0];
			int ty = que[head].y + dis[i][1];
			//cout << flag[0].size() << flag.size();
			//cout << map[tx][ty] << flag[tx][ty];
			if (tx<m && tx >= 0 && ty<n && ty >= 0 && map[tx][ty] == 0)
			if (flag[tx][ty] == 0)
			{
				que[tail].x = tx;
				que[tail].y = ty;
				que[tail].pre = head;
				flag[tx][ty] = 1;
				if (tx == EN.x && ty == EN.y)
				{
					//head is the first step to the end point.
					return tail;
				}
				tail++;
			}
		}
		head++;
	}
	return 0;
}

int main()
{
	while (cin >> m >> n)
	{
	node *que = new node[n*m];
        head = 0; tail = 1;
		start.x = 0; start.y = 0; start.pre = -1;
		EN.x = m - 1; EN.y = n - 1; EN.pre = -1;
		vector<vector<int>> map(m, vector<int>(n, 0));
		for (int i = 0; i<m; i++){
			for (int j = 0; j<n; j++)
			{
				cin >> map[i][j];
			}
		}
		int tail = BFS(map, que);
        print_path(tail, que);
		delete []que;
	}
		
	return 0;
}