题目描述 一个N×N的棋盘，每个格子填有1、2、3、4中的某一个。最开始在左上角放一个棋子，每次可以移动至上、下、左、右四个格子中的某一个，每次只能移动一格（允许重复移动到某一个格子），在任何时刻都不允许将棋子移除棋盘。在移动时需要进行计分。如果初始格子中的数字为X，目标格子中的数字为Y，则本次移动计分为|X - Y|。现在需要把棋子移动到右下角，求最小计分。
输入描述 第一行为nn 第二行到第n+1n+1行，为一个二维数组，表示棋盘上的每个格子对应的数字（正整数）。
1≤n≤1001≤n≤100 输出描述 最小计分。
样例：
输入：
3 1 2 4 1 3 1 1 2 1输出：
2
思路：dijkstra 堆优化版本。O(mlogn), 输入部分是n2
#include <iostream> #include <queue> #include <string.h> using namespace std; const int N = 110; const int M = N * N; //点个数 int n; int g[N][N]; //权值列表 int h[M], e[M * 4], w[M * 4], ne[M * 4], idx; //邻接表 int dist[M]; //最短路径状态列表 int st[M]; //搜索完毕点集 int move_i[4] = {1, 0, -1, 0}; //上下左右移动数组 int move_j[4] = {0, 1, 0, -1}; int start, ed; // 起点终点 void add(int a, int b, int c) { //构建邻接表 e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } int get_line_map(int i, int j) { //矩阵拉成一维数组映射 return n * (i - 1) + j; } void dijkstra(){ memset(dist, 0x3f, sizeof(dist)); //dist初状态为全部无穷大 dist[start] = 0; //起点0，的dist为0 priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> q; q.push(make_pair(0, start)); while(!q.empty()){ auto t = q.top(); q.pop(); int dis = t.first; int vel = t.second; if(st[vel]) { continue; } st[vel] = 1; for(int i = h[vel]; i != -1; i = ne[i]) { //当前放入节点出度节点距离更新 int j = e[i]; //邻接表中的下一个节点 if(dist[j] > w[i] + dis){ //w[i]为vel到j的权值。dist中记录的值比新路径大，更新，推进堆 dist[j] = w[i] + dis; q.push(make_pair(dist[j], j)); } } } } int main() { cin>>n; for(int i = 1;i <= n; i++) { for(int j = 1; j <= n; j++) { cin>>g[i][j]; } } start = get_line_map(1, 1); ed = get_line_map(n, n); memset(h, -1, sizeof(h)); for(int i = 1;i <= n; i++) { for(int j = 1; j <= n; j++) { for(int k = 0; k < 4; k++){ int a = i + move_i[k]; int b = j + move_j[k]; if(a <= 0 || a > n || b <= 0 || b > n) { continue; } add(get_line_map(i ,j), get_line_map(a, b), abs(g[i][j] - g[a][b])); } } } dijkstra(); if(dist[ed] == 0x3f3f3f3f) { //无穷大，没有通路 dist[ed] = -1; } cout<<dist[ed]<<endl; return 0; }
