问题1：寻找最优路径【Breadth First Search】
这个和贪婪算法不一样，这个属于遍历所有节点
假设以一个n*m的矩阵作为棋盘，每个棋位对应一个二维坐标 (x, y)。
你有一颗棋子位于左上起点(0, 0)，现在需要将其移动到右下底角 (n-1, m-1)，
棋子可以向相邻的上下左右位置移动，每个坐标最多只能经过一次。
棋盘中散布着若干障碍，障碍物不能跨越，只能绕行，问是否存在到达右下底角的路线？若存在路线，输出所需的最少移动次数；
若不存在，输出0。
Input 第一行三个正整数n，m和k，代表棋盘大小与障碍物个数 1< n、m < 100, k < n*m 第二行至第k+1行，
每行为两个整数x和y，代表k个障碍物的坐标。
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
class Loc{
int x,y,step;
public Loc(int x,int y,int step){
this.x=x;
this.y=y;
this.step=step;
}
}
public class Main {//应该是要使用到广度搜索算法
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),m=sc.nextInt(),k=sc.nextInt();
int[][] map=new int[n][m];
for(int i=0;i<k;i++){
map[sc.nextInt()][sc.nextInt()]=1;
}
int ans=0;
Queue<Loc> queue=new LinkedList<Loc>();
queue.add(new Loc(0,0,0));
while (queue.size()>0){
Loc pre=queue.poll();
if(pre.x==n-1&&pre.y==m-1){//到达终点
// System.out.println("到达终点");
ans=pre.step;
break;
}
map[pre.x][pre.y]=1;
//向右
if(pre.y+1<m&&map[pre.x][pre.y+1]==0){
queue.add(new Loc(pre.x,pre.y+1,pre.step+1));
}
//向下
if(pre.x+1<n&&map[pre.x+1][pre.y]==0){
queue.add(new Loc(pre.x+1,pre.y,pre.step+1));
}
//向左
if(pre.y-1>=0&&map[pre.x][pre.y-1]==0){
queue.add(new Loc(pre.x,pre.y-1,pre.step+1));
}
//向上
if(pre.x-1>=0&&map[pre.x-1][pre.y]==0){
queue.add(new Loc(pre.x-1,pre.y,pre.step+1));
}
}
System.out.println(ans);
}
}
问题2：寻找最优路径-变形【Breadth First Search】
薯队长最近在玩一个迷宫探索类游戏，迷宫是一个N*N的矩阵形状，
其中会有一些障碍物禁止通过。这个迷宫还有一个特殊的设计，
它的左右边界以及上下边界是连通的，比如在(2,n)的位置继续往右走一格可以到(2,1)，
在(1,2)的位置继续往上走一格可以到(n,2)。
请问薯队长从起点位置S，最少走多少格才能到达迷宫的出口位置E。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Loc{
int x,y,step;
public Loc(int x,int y,int step){
this.x=x;
this.y=y;
this.step=step;
}
}
public class Main2 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int[][] sinMap=new int[N][N];
int[][] map=new int[N*3][N*3];
String temp;
int value=0;
int[] index0=new int[2];
for(int i=0;i<N;i++){
temp=sc.next();
for(int j=0;j<N;j++){
// System.out.println("j:"+j+",temp:"+temp+",char:"+temp.charAt(j));
switch (temp.charAt(j)){
case '.':
value=0;
break;
case '#':
value=-1;
break;
case 'S':
value=1;
break;
case 'E':
value=2;
break;
}
if(value==-1){
sinMap[i][j]=-1;
}else if(value==1){
index0[0]=i+N;
index0[1]=j+N;
}else if(value==2){
sinMap[i][j]=1;
}
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
//sinMap块进行复制粘贴
for(int ii=0;ii<N;ii++) {
for (int jj = 0; jj < N; jj++) {
map[i*N+ii][j*N+jj]=sinMap[ii][jj];
}
}
}
}
N*=3;
int ans=0;
Queue<Loc> queue=new LinkedList<Loc>();
queue.add(new Loc(index0[0],index0[1],0));
while (queue.size()>0){
Loc pre=queue.poll();
map[pre.x][pre.y]=-1;
//向右
if(pre.y+1<N&&map[pre.x][pre.y+1]!=-1){
if(map[pre.x][pre.y+1]==1){
ans=pre.step+1;
break;
}
queue.add(new Loc(pre.x,pre.y+1,pre.step+1));
}
//向下
if(pre.x+1<N&&map[pre.x+1][pre.y]!=-1){
if(map[pre.x+1][pre.y]==1){
ans=pre.step+1;
break;
}
queue.add(new Loc(pre.x+1,pre.y,pre.step+1));
}
//向左
if(pre.y-1>=0&&map[pre.x][pre.y-1]!=-1){
if(map[pre.x][pre.y-1]==1){
ans=pre.step+1;
break;
}
queue.add(new Loc(pre.x,pre.y-1,pre.step+1));
}
//向上
if(pre.x-1>=0&&map[pre.x-1][pre.y]!=-1){
if(map[pre.x-1][pre.y]==1){
ans=pre.step+1;
break;
}
queue.add(new Loc(pre.x-1,pre.y,pre.step+1));
}
}
System.out.println(ans);
}
}
/*
4
#S..
.#..
.E..
##..
*/
问题3：带权重的最优路径规划【标准的贪婪算法】
每次只选择最小的数据进行运行，有一个优先队列