6分求条
查看原帖
6分求条
1747567
shihanyu2013楼主2025/7/28 20:45
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,head[2000001],dis[2000001],vis[2000001];
char c;
struct edge{
    int v,nxt,w;
}e[2000001];
struct node{
    int id,d;
    bool operator <(const node &nd) const {
		return d>nd.d;
	}
};
priority_queue<node>q;
void add(int u,int v,int w){
    e[++cnt]={v,head[u],w};
    head[u]=cnt;
}
void dijkstra(int d){
    dis[d]=0;
    q.push({d,0});
    while(q.size()){
        int t=q.top().id;
        q.pop();
        if(vis[t]) continue;
        vis[t]=1;
        for(int i=head[t];i;i=e[i].nxt){
            int v=e[i].v;
            dis[v]=min(dis[v],dis[t]+e[i].w);
			if(!vis[v]) q.push({v,dis[v]});
        }
    }
}
signed main(){
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c;
            int f;
            if(c=='\\') f=0;
            else f=1;
            int v=i*(m+1)+j,u=(i+1)*(m+1)+j+1;
            add(v,u,f);
            add(u,v,f);
            v=(i+1)*(m+1)+j,u=i*(m+1)+j+1;
            add(v,u,f^1);
            add(u,v,f^1);
        }
    }
    dijkstra(0);
    int ans=0;
    if(dis[(n+1)*(m+1)-1]==0x3f3f3f3f){
        puts("NO SOLUTION");
    } else cout<<dis[n*m+2*m];
    return 0;
}
2025/7/28 20:45
加载中...