这思路哪里错了?
查看原帖
这思路哪里错了?
246979
SalomeJLQ楼主2020/8/10 16:03

我的思路:

用广搜遍历,如果一个点被第一次搜索到,把这个点标记为一个标号,然后连边,入队;如果被少于等于4次搜索到,那么就只连边,并且不入队;如果遇到了一个传送门,那么就连一条权值为0的边,然后跑dijkstra

下面是代码(极度冗长):

#include<bits/stdc++.h>
using namespace std;
char a[305][305],visit[305][305];
int n,m,qd,zd,dbh[305][305];
int bian[305][305];
int cnt,head[100005];
void add(int u,int v,int w){bian[u][v]=w;}
int dis[100005];
struct node{
    int u,d;
    bool operator<(const node& rhs)const{return d>rhs.d;}
};
void dijkstra(int kaishi,int jieshu){
    for(int i=1;i<=n;i++)dis[i]=2147483647;
    dis[kaishi]=0;
    priority_queue<node>Q;
    Q.push((node){kaishi,0});
    while(!Q.empty()){
        node fr=Q.top();Q.pop();
        int u=fr.u,d=fr.d;
        if(d!=dis[u])continue;
        for(int i=1;i<=n;i++){
			if(bian[u][i]!=-1){
            	int w=bian[u][i];
	            if(dis[u]+w<dis[i]){
    	            dis[i]=dis[u]+w;
        	        Q.push((node){i,dis[i]});
            	}
			}
        }
    }
}
void findd(char ch,int xx,int yy,int bhq,int bhz){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]==ch){
				visit[i][j]++;
				add(bhq,bhz,0);
			}
}
void build(int x,int y){
	queue<int>qx;queue<int>qy;
	qx.push(x);qy.push(y);
	int bh=0;
	dbh[x][y]=++bh;
	while(!qx.empty()){
		int dqx=qx.front();qx.pop();
		int dqy=qy.front();qy.pop();
		if(visit[dqx+1][dqy]<4){
			if(a[dqx+1][dqy]=='.'||a[dqx+1][dqy]=='@'){
				if(!dbh[dqx+1][dqy]){
					dbh[dqx+1][dqy]=++bh;
					add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
					visit[dqx+1][dqy]++;
					qx.push(dqx+1);qy.push(dqy);
				}
				else{
					add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
					visit[dqx+1][dqy]++;
				}
			}
			if(a[dqx+1][dqy]=='='){
				dbh[dqx+1][dqy]=++bh;
				add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
				visit[dqx+1][dqy]++;
			}
			if(a[dqx+1][dqy]<='Z'&&a[dqx+1][dqy]>='A'){
				if(!dbh[dqx+1][dqy]){
					dbh[dqx+1][dqy]=++bh;
					add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
					visit[dqx+1][dqy]++;
					findd(a[dqx+1][dqy],dqx+1,dqy,dbh[dqx][dqy],dbh[dqx+1][dqy]);
				}
				else{
					add(dbh[dqx][dqy],dbh[dqx+1][dqy],1);
					visit[dqx+1][dqy]++;
				}
			}
		}
		if(visit[dqx-1][dqy]<4){
			if(a[dqx-1][dqy]=='.'||a[dqx-1][dqy]=='@'){
				if(!dbh[dqx-1][dqy]){
					dbh[dqx-1][dqy]=++bh;
					add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
					visit[dqx-1][dqy]++;
					qx.push(dqx-1);qy.push(dqy);
				}
				else{
					add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
					visit[dqx-1][dqy]++;
				}
			}
			if(a[dqx-1][dqy]=='='){
				dbh[dqx-1][dqy]=++bh;
				add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
				visit[dqx-1][dqy]++;
			}
			if(a[dqx-1][dqy]<='Z'&&a[dqx-1][dqy]>='A'){
				if(!dbh[dqx-1][dqy]){
					dbh[dqx-1][dqy]=++bh;
					add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
					visit[dqx-1][dqy]++;
					findd(a[dqx-1][dqy],dqx-1,dqy,dbh[dqx][dqy],dbh[dqx-1][dqy]);
				}
				else{
					add(dbh[dqx][dqy],dbh[dqx-1][dqy],1);
					visit[dqx-1][dqy]++;
				}
			}
		}
		if(visit[dqx][dqy+1]<4){
			if(a[dqx][dqy+1]=='.'||a[dqx][dqy+1]=='@'){
				if(!dbh[dqx][dqy+1]){
					dbh[dqx][dqy+1]=++bh;
					add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
					visit[dqx][dqy+1]++;
					qx.push(dqx);qy.push(dqy+1);
				}
				else{
					add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
					visit[dqx][dqy+1]++;
				}
			}
			if(a[dqx][dqy+1]=='='){
				dbh[dqx][dqy+1]=++bh;
				add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
				visit[dqx][dqy+1]++;
			}
			if(a[dqx][dqy+1]<='Z'&&a[dqx][dqy+1]>='A'){
				if(!dbh[dqx][dqy+1]){
					dbh[dqx][dqy+1]=++bh;
					add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
					visit[dqx][dqy+1]++;
					findd(a[dqx][dqy+1],dqx-1,dqy,dbh[dqx][dqy],dbh[dqx][dqy+1]);
				}
				else{
					add(dbh[dqx][dqy],dbh[dqx][dqy+1],1);
					visit[dqx][dqy+1]++;
				}
			}
		}
		if(visit[dqx][dqy-1]<4){
			if(a[dqx][dqy-1]=='.'||a[dqx][dqy-1]=='@'){
				if(!dbh[dqx][dqy-1]){
					dbh[dqx][dqy-1]=++bh;
					add(dbh[dqx][dqy],dbh[dqx][dqy-1],1);
					visit[dqx][dqy-1]++;
					qx.push(dqx);qy.push(dqy-1);
				}
				else{
					add(dbh[dqx][dqy],dbh[dqx][dqy-1],1);
					visit[dqx][dqy-1]++;
				}
			}
			if(a[dqx][dqy-1]=='='){
				dbh[dqx][dqy-1]=++bh;
				add(dbh[dqx][dqy],dbh[dqx][dqy-1],1);
				visit[dqx][dqy-1]++;
			}
			if(a[dqx][dqy-1]<='Z'&&a[dqx][dqy-1]>='A'){
				if(!dbh[dqx][dqy-1]){
					dbh[dqx][dqy-1]=++bh;
					add(dbh[dqx][dqy],dbh[dqx][dqy-1],1);
					visit[dqx][dqy-1]++;
					findd(a[dqx][dqy-1],dqx-1,dqy,dbh[dqx][dqy],dbh[dqx][dqy-1]);
				}
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			bian[i][j]=-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)cin>>a[i][j];
	int bj=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			if(a[i][j]=='.'){build(i,j);bj=1;break;}
		if(bj)break;
	}
	int qishi,jieshu;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(a[i][j]=='@')qishi=dbh[i][j];
			if(a[i][j]=='=')jieshu=dbh[i][j];
		}
	dijkstra(qishi,jieshu);
	cout<<dis[jieshu];
	return 0;
}
2020/8/10 16:03
加载中...