记忆化广度优先搜索

#include <bits/stdc++.h>
using namespace std;
struct pre{
	int x,y;
};
int val[37][37];
int w[37][37];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
int n,m;
queue<pre>q;
void bfs(){
	q.push({1,1});
	while(!q.empty()){
		for(int i=0;i<4;i++){
			int xx=q.front().x+dx[i],yy=q.front().y+dy[i];
			if(xx>0&&xx<=n&&yy>0&&yy<=m&&val[q.front().x][q.front().y]+w[xx][yy]<val[xx][yy]){
				val[xx][yy]=val[q.front().x][q.front().y]+w[xx][yy];
				q.push({xx,yy});
			}
		}
		q.pop();
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>w[i][j];
		}
	}
	memset(val,0x3f3f3f3f,sizeof(val));
	val[1][1]=w[1][1];
	bfs();
	cout<<val[n][m];
	return 0;
}