还请各路大神帮我对照以下两个代码:
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;
}