Title Description

For a positive integer matrix M of n * n (n < = 100), there is a sequence of adjacent terms from M[A1, B1] to M[A2, B2]. Two adjacent terms M[x1,y1] and M[x2,y2] mean that the conditions are met: ә x1-x2| + ә y1-y2 ә = 1 and 1 < = x1, Y1, X2, Y2 < = n

Your task: input matrix M, A1, B1 and A2, B2 values from the file. Find the sequence of adjacent terms from M[A1,B1] to M[A2,B2], so that the sum of the absolute values of the difference between adjacent terms is the minimum.

Analysis

At first glance, it feels like a Dp problem, but Dp has its aftereffect. After reading the question again, it is found that the range of n is relatively small, so for each element in the matrix, the edge weight is the absolute value of the difference between two adjacent elements, and then the shortest path can be run from the starting point.

Code

#include <cstdio>
#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100*100+5;
struct Edge {
	int to,next,weight;
}e[N*10];
int h[N],cnt;
int n;
int g[101][101];
int nxt[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int d[N],vis[N];
void add(int x,int y,int z) {
	e[++cnt]=(Edge){y,h[x],z};
	h[x]=cnt;
}
int getnum(int i,int j) {//Coordinate conversion No 
	return n*(i-1)+j;
}
void spfa(int v0) {
	memset(vis,0,sizeof vis);
	memset(d,0x3f,sizeof d);
	d[v0]=0;
	vis[v0]=1;
	queue<int> q;
	q.push(v0);
	while (!q.empty()) {
		int t=q.front();
		q.pop();
		vis[t]=0;
		for (int i=h[t];i;i=e[i].next) {
			int y=e[i].to;
			if (d[y]>d[t]+e[i].weight) {
				d[y]=d[t]+e[i].weight;
				if (!vis[y]) {
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++) scanf("%d",&g[i][j]);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			for (int k=0;k<4;k++) {
				int tx=i+nxt[k][0],ty=j+nxt[k][1];
				if (tx<=0||tx>n||ty<=0||ty>n) continue;
				add(getnum(i,j),getnum(tx,ty),abs(g[i][j]-g[tx][ty]));
				//Only one-way edge is built, because the node at the back will loop to this node again 
			}
	int sx,sy,gx,gy;
	int snum,gnum;
	scanf("%d%d%d%d",&sx,&sy,&gx,&gy);
	snum=getnum(sx,sy);
	gnum=getnum(gx,gy);
	spfa(snum);
	printf("%d",d[gnum]);
	return 0;
}