Q：为什么要用Dijkstra做？而不是bfs？

A：闲的（

以上结尾废话↑

实在不行我换成bfs做

记录

思路：在地图中如果遇到0，就向上和向左建边，如果那两个点也是0。然后做dij。

把二维的坐标转换成一维的坐标没什么问题，就是建边时有点问题，应该是有向图，求调QAQ

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int INF=1e9;
int n,m,s,t,cnt; 
struct Edge{
	int v,w;
	Edge(int v,int w):v(v),w(w){}
};
struct Node{
	int u,d;
	Node(int u,int d):u(u),d(d){}
	bool operator < (const Node &a) const{
		return d>a.d;
	}
};
int d[N],vis[N];
char a[1005][1005];
vector<Edge> adj[N];
void dij(){
	for(int i=1;i<=n;i++)d[i]=INF;
	d[s]=0;
	priority_queue<Node>q;
	q.push(Node(s,0));
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(u==t)return;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<adj[u].size();i++){
			int v=adj[u][i].v;
			int w=adj[u][i].w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				q.push(Node(v,d[v]));
			}
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
			int u=(i-1)*n+j,v,w=1;
			if(i==1)continue; 
			if(a[i][j]=='1')continue;
			if(a[i-1][j]=='0'){
				v=(i-2)*n+j;
				adj[u].push_back(Edge(v,w));
				adj[v].push_back(Edge(u,w));
			}
			if(a[i][j-1]=='0'){
				v=(i-1)*n+(j-1);
				adj[u].push_back(Edge(v,w));
				adj[v].push_back(Edge(u,w));
			}
		}
	}
	int s1,s2,t1,t2;
	cin>>s1>>s2>>t1>>t2;
	s=(s1-1)*n+s2,t=(t1-1)*n+t2;
	dij();
	cout<<d[t];
    return 0;
}