格子里的整数-贪心算法
Description
Given a square grid of size n, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which total cost incurred is minimum.
Note : It is assumed that negative cost cycles do not exist in input matrix.
Input
The first line of input will contain number of test cases T. Then T test cases follow . Each test case contains 2 lines. The first line of each test case contains an integer n denoting the size of the grid. Next line of each test contains a single line containing N*N space separated integers depecting cost of respective cell from (0,0) to (n,n).
Constraints:1<=T<=50，1<= n<= 50
Output
For each test case output a single integer depecting the minimum cost to reach the destination.
Sample Input 1
2 5 31 100 65 12 18 10 13 47 157 6 100 113 174 11 33 88 124 41 20 140 99 32 111 41 20 2 42 93 7 14
Sample Output 1
327 63
解题思路：
看到题目开始以为是动态规划，用递推求出。但细看发现点的移动方向不固定，可以朝任意方向移动。发现题目给定矩阵也可以转换成图，题目其实是单端最短路径的一种变体。
这里需要将输入的矩阵转换一下，转换成邻接矩阵，不相邻的点距离设置为最大。
得到邻接矩阵后，剩下的就是用dijkstra方法求最短路径。
这里顺带说下dijkstra，其把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。每次将一个点加入S后，更新U中所有点的最短路径。
算法需要的数据结构：
visited[] 为false表示在集合U中，为true表示在集合S中。
dis[] ，dis[i]表示第i个点距离初始点的最短距离，不相邻的点初始值为无穷大。
acc[][], 邻接矩阵，arr[i][j]表示第i个点与第j个点的最短距离，不相邻的点初始值为无穷大。
算法步骤：
1.首先初始化arr[][]和dis[]，将初始点加入S，visited[0]置为true；
2.将U中dis[i]最小的点p加入到S中。
3.遍历U中所有的点，如果存在某一个点q，使得dis[p][q] + dis[p] < dis[q],则更新dis[q];
4.重新返回步骤2，直到所有的点都已经加入到集合S。
实现代码如下：
1 import java.util.*; 2 3 public class Main { // 注意类名必须为Main 4 public static int max = 1000000; 5 public static void main(String[] args) { 6 Scanner scan = new Scanner(System.in); 7 int number = scan.nextInt(); 8 scan.nextLine(); 9 // number个测试样例 10 for (int k = 0; k < number; k++){ 11 // 输入数据 12 int n = scan.nextInt(); 13 int[][] arr = new int[n][n]; 14 for (int i = 0; i < n; i++) { 15 for (int j = 0; j < n; j++) { 16 arr[i][j] = scan.nextInt(); 17 } 18 } 19 // 初始化acc[][] 20 int size = n*n; 21 int[][] acc = new int[size][size]; 22 for (int i = 0; i < size; i++) 23 for (int j = 0; j < size; j++) 24 acc[i][j] = max; 25 int[][] temp = {{-1,0},{1,0},{0,-1},{0,1}}; 26 for (int i = 0; i < n; i++) 27 for (int j = 0; j < n; j++) { 28 // 点arr[i]本身赋值 29 int index = transform(i, j, n); 30 acc[index][index] = arr[i][j]; 31 // 点arr[i]相邻的点赋值 32 for (int q = 0; q < temp.length; q++) { 33 int X = i+temp[q][0]; 34 int Y = j+temp[q][1]; 35 if (X >=0 && X < n && Y >= 0 && Y < n) { 36 acc[transform(X,Y,n)][index] = arr[i][j]; 37 } 38 } 39 } 40 // 获得结果 41 int[] dis = dijkstra(acc); 42 System.out.println(arr[0][0]+dis[size-1]); 43 } 44 } 45 // 将i,j转为index 46 public static int transform(int i, int j, int n) { 47 return i*n+j; 48 } 49 // 根据顶点的邻接矩阵，使用djikstra算法计算出初始点到各个点的最短路径 50 public static int[] dijkstra(int[][] acc) { 51 // 初始化dis[] 52 int size = acc.length; 53 int[] dis = new int[size]; 54 for (int i = 0; i < size; i++) 55 dis[i] = acc[0][i]; 56 boolean[] visited = new boolean[size]; 57 visited[0] = true; 58 // 执行size-1次操作，可以找到所有点的最短路径值 59 for (int i = 1; i < size; i++) { 60 // 找到集合V中dis[i]最小的点p 61 int min = max; 62 int p = -1; 63 for (int j = 0; j < size; j++) { 64 if (!visited[j] && dis[j] < min) { 65 p = j; 66 min = dis[j]; 67 } 68 } 69 // 将点p加入到集合S中 70 visited[p] = true; 71 // 更新所有集合V中的点q,dis[q] = Math.min(dis[q], dis[p]+acc[p][q]) 72 for (int q = 0; q < size; q++) { 73 if (!visited[q] && (dis[p] + acc[p][q] < dis[q])) { 74 dis[q] = dis[p] + acc[p][q]; 75 // 如果更新到了终点，直接返回结果，不用再执行后续更新 76 if (q == size-1) 77 return dis; 78 } 79 } 80 } 81 // 返回结果 82 return dis; 83 } 84 }
版权声明：本文为ningbing原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。