求助
  • 板块灌水区
  • 楼主lyc20110701
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/25 17:31
  • 上次更新2024/7/25 18:57:18
查看原帖
求助
1126841
lyc20110701楼主2024/7/25 17:31

还请各路大神帮我对照以下两个代码:

A

#include<iostream>
#include<cstdio>
#include<utility>
#include<vector>
#include<functional>
#include<cstring>
#include<queue>
using namespace std;
int n,m,T;
char ch[505][505];
int dx[]={-1,+1,+1,-1}; // 计算【格点坐标】的增量数组。从右上角开始,顺时针旋转
int dy[]={+1,+1,-1,-1};
int gx[]={-1,0,0,-1}; // 计算【网孔坐标】的增量数组。从右上角开始,顺时针旋转
int gy[]={0,0,-1,-1};
int h[1000000];
int nt[1000000];
int to[1000000];
int w[1000000];
int idx;
int d[250005];
bool v[250005];
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > hp;
char should[]="/\\/\\";
void init(){
	memset(v,0,sizeof(v));
	memset(d,0x3f,sizeof(d));
	memset(h,-1,sizeof(h));
	idx=0;
}

void add(int x,int y,int z){
	to[idx]=y;
	nt[idx]=h[x];
	w[idx]=z;
	h[x]=idx;
	idx++;
}

void make_tu(){
	for(int x=0;x<=n;x++){
		for(int y=0;y<=m;y++){
			int k=x*(m+1)+y;
			for(int i=0;i<4;i++){ 
			int zx=x+dx[i],zy=y+dy[i];
			if(zx<0||zx>n||zy<0||zy>m) continue;
			int t=zx*(m+1)+zy;
			int px=gx[i]+x,py=gy[i]+y;
			if(px<0||px>=n||py<0||py>=m) continue;
			add(k , t , ch[px][py]!=should[i] );
			} 
		}
	}
}

int dijkstra_hp(int u){
	d[u]=0;
	hp.push((PII){0,u});
	while(hp.size()>0){
		PII P=hp.top();
		hp.pop();
		int dist=P.first;
		int t=P.second;
		if(!v[t]){
			v[t]=true;
			for(int i=h[t];i!=-1;i=nt[i]){
				int j=to[i];
				if(dist+w[i]<d[j]){
					d[j]=dist+w[i];
					hp.push ((PII) {d[j],j});
				}
			}
		}
	}
	return d[(n+1)*(m+1)-1];
		
}


int main(){
	scanf("%d",&T);
	while(T--){
		cin>>n>>m;
		init();
		for(int i=0;i<n;i++){
			scanf("%s",ch[i]);
		}
		if((n+m)%2==1){
			puts("NO SOLUTION");
			continue;
		}
		make_tu();
		int ans=dijkstra_hp(0); 
		printf("%d\n",ans);
	}
	
	
	
	
	return 0;
}

B

#include<iostream>
#include<cstdio>
#include<utility>
#include<vector>
#include<functional>
#include<cstring>
#include<queue>
using namespace std;

// 解法一:dijkstra算法求解

/*
1.建图。
 	1.1 建立节点:一共有(n+1)*(m+1)个节点,从做导游,从上到下,依次编号为0,1,2,..., (n+1)*(m+1)-1
 	1.2 建边
	 	1.2.1 每个点最多发出4条边,根据n,m的取值范围,本题需要建立100万条边就足够了
		1.2.2 使用链式前向星存储图
		1.2.3 遍历每一个节点,
2.注意cout<<'\\'<<endl; // 两个\\表示一个\


*/

int T,n,m;

// 多组测试用例,立马想到写init()!!

int h[1000000];
int to[1000000];
int nt[1000000];
int w[1000000];

int idx;

void add(int x, int y, int z){
	to[idx]=y;
	w[idx]=z;
	nt[idx]=h[x];
	h[x]=idx;
	idx++;
}

char a[510][510];

int dx[]={-1,+1,+1,-1}; // 计算【格点坐标】的增量数组。从右上角开始,顺时针旋转
int dy[]={+1,+1,-1,-1};

int gx[]={-1,0,0,-1}; // 计算【网孔坐标】的增量数组。从右上角开始,顺时针旋转
int gy[]={0,0,-1,-1};

char should[]="/\\/\\";

// 建图函数
void build_graph(){
	for(int x=0;x<=n;x++){ // 注意此处可以等于n
		for(int y=0;y<=m;y++){ // 注意此处可以等于m
			// 1.计算出(x,y)格点所代表的图的节点的编号k
			int k=x*(m+1)+y;
			for(int i=0;i<4;i++){

				// (zx,zy)这个是格点的坐标
				int zx=x+dx[i],zy=y+dy[i];
				if(zx<0||zx>n||zy<0||zy>m) continue;

				int t=zx*(m+1)+zy;

				// 获取对应网孔的值
                int px=x+gx[i],py=y+gy[i]; // gx,gy为对应网孔的坐标
                // 网孔坐标在格点坐标合法的情况下,也一定合法

                if(px<0||px>=n||py<0||py>=m) continue;

				add(k,t, a[px][py]!=should[i] ); // 注意,此处只需加一次边即可
			}
		}
	}
}

int d[250000+10];
bool v[250000+10]; // [bitset]
typedef pair<int,int> PII;

void init(){
    // 重置链式前向星
    memset(h,-1,sizeof(h));
    idx=0;
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
}

priority_queue<PII,vector<PII>,greater<PII> > hp;

int dijkstra_heap(int u){
    d[u]=0;
    hp.push((PII){0,u});
    while(hp.size()>0){
        PII p=hp.top();
        hp.pop();
        int dist=p.first;
        int t=p.second;
        if(!v[t]){
            v[t]=true;
            for(int i=h[t];i!=-1;i=nt[i]){
                int j=to[i];
                if(dist+w[i]<d[j]){
                    d[j]=dist+w[i];
                    hp.push((PII){d[j],j});
                }
            }
        }
    }
    return d[(n+1)*(m+1)-1]; // 下标是从0开始的
}

int main(){

	cin>>T;
	while(T--){
		scanf("%d%d",&n,&m);

		// 否则就说明一定有解

		for(int i=0;i<n;i++){ // 下标均从0开始
			scanf("%s",a[i]);
		}
        init(); // 初始化函数不要忘记调用

		 
		//【务必注意本题的continue之前必须要把输入写完!!】 
        if((n+m)%2==1){ // 终点的坐标之和为奇数,则说明无论如何到达不了终点
            puts("NO SOLUTION");
            continue;
		}

        build_graph();

        int ans=dijkstra_heap(0);
        printf("%d\n",ans);
	}

	return 0;
}
2024/7/25 17:31
加载中...