DFS

#include<bits/stdc++.h>
using namespace std;

int n, m; 
int g[110][110], vis[110][110], dist[110][110]; // g存图,vis标记x,y是否走过，dist记录起点到x,y的最短距离
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0}; // 方向数组

bool check(int nx, int ny) 
{
  // 没有越界，没有来过，且不是墙
  if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] == 0) 
    return true;
  return false;
}

void dfs(int x, int y)
{
	if (x == n && y == m) // 边界判定
	{
		return;
	}
	for (int i = 0; i < 4; i++) // 循环4个方向
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (check(nx, ny) && dist[x][y] + 1 < dist[nx][ny]) // 可行性判定并进一步搜索
		{
			vis[nx][ny] = 1; // 标记
			dist[nx][ny] = dist[x][y] + 1; // 更新最短路
			dfs(nx, ny); // 递归搜索
			vis[nx][ny] = 0; // 回溯
		}
	}
}

int main()
{
	memset(dist, 0x3f, sizeof dist); // 初始化极大值
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j++)
			cin >> g[i][j];
	vis[1][1] = 1; // 起点标记
	dist[1][1] = 0; // 初始化距离
	dfs(1,1); 
	cout << dist[n][m];
	
	return 0;
}

BFS

#include<bits/stdc++.h>
using namespace std;

int n, m; 
int g[110][110], vis[110][110], dist[110][110]; // g存图,vis标记x,y是否走过，dist记录起点到x,y的最短距离
int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0}; // 方向数组

bool check(int nx, int ny) 
{
  // 没有越界，没有来过，且不是墙
  if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis[nx][ny] && g[nx][ny] == 0) 
    return true;
  return false;
}

void bfs()
{
	/*
	1.起点入队
	2.当队列不为空，弹出队头元素，并拓展队头
	3.重复2，直到队列为空
	4.输出答案
	*/
	queue<pair<int,int>> q;
	q.push({1,1});
	vis[1][1] = 1; // 起点标记
	dist[1][1] = 0; // 初始化距离
	while (q.size())
	{
		auto t = q.front(); q.pop();
		int x = t.first, y = t.second;
		if (x == n && y == m) return;
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i], ny = y + dy[i];
			if (check(nx, ny))
			{
				vis[nx][ny] = 1;
				q.push({nx, ny});
				dist[nx][ny] = dist[x][y] + 1;
			}
		}
	}
}

int main()
{
	memset(dist, 0x3f, sizeof dist); // 初始化极大值
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j++)
			cin >> g[i][j];
	bfs(); 
	cout << dist[n][m];
	
	return 0;
}