这里是引用题目描述:QAUer住在西苑，有一天他起晚了，眼看要迟到了，他要赶快赶到东苑教学区上课，西苑和东苑教学区必须要经过地下通道。请你为他寻找一条最短的路径，使他快速赶到教学区。 Input: 输入一个n代表n * n地图，接下来n行输入地图.’S’表示西苑，’L’表示地下通道,’T’表示东苑教学区.’.’代表可走道路，’#’表示障碍物，不可走. Ouput: 输出一个数，代表最短路径长度.保证必定存在可行解。 Sample input : 4 S.#. …#. .L.# …T. Sample output : 5
先从S到L做一次BFS，再从T到L做一次BFS，求出S->L的最短路和T->L的最短路相加即为答案.同时,本题也可以使用DFS做,但要注意剪枝.(如果存在比当前最短路大的路径,直接return).
c++
#include<iostream> #include<queue> #define Maxn 105 using namespace std; struct Node { int x; int y; int step; }; int vis[Maxn][Maxn]; int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; char a[Maxn][Maxn]; int n; int tx, ty, sx, sy, dx, dy, ans1 = 0, ans2 = 0; int main() { queue<Node>q; cin >> n; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin >> a[i][j]; if(a[i][j] == 'S') { sx = i; sy = j; } if(a[i][j] == 'T') { tx = i; ty = j; } if(a[i][j] == 'L') { dx = i; dy = j; } } } Node node; node.x = sx, node.y = sy, node.step = 0; q.push(node); while(!q.empty()) { Node nd = q.front();q.pop(); if(nd.x == dx && nd.y == dy) { ans1 = nd.step; break; } for(int i = 0;i < 4;i++) { int nx = nd.x + dir[i][0]; int ny = nd.y + dir[i][1]; if(nx < 0 || nx >= n || ny <0 || ny >= n || vis[nx][ny] == 1 || a[nx][ny] == '#')continue; vis[nx][ny] = 1; Node node1;node1.x = nx,node1.y = ny,node1.step = nd.step + 1; q.push(node1); } } while(!q.empty())q.pop(); for(int i = 0;i < n;i++) for(int j = 0;j < n;j++)vis[i][j] = 0; node.x = tx, node.y = ty, node.step = 0; q.push(node); while(!q.empty()) { Node nd = q.front();q.pop(); if(nd.x == dx && nd.y == dy) { ans2 = nd.step; break; } for(int i = 0;i < 4;i++) { int nx = nd.x + dir[i][0]; int ny = nd.y + dir[i][1]; if(nx < 0 || nx >= n || ny <0 || ny >= n || vis[nx][ny] == 1 || a[nx][ny] == '#')continue; vis[nx][ny] = 1; Node node1;node1.x = nx,node1.y = ny,node1.step = nd.step + 1; q.push(node1); } } cout << ans1 + ans2 << endl; return 0; }Java
import java.math.BigInteger; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Comparator; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static class Node{ int x, y, step; Node(int x, int y, int step){ this.x = x; this.y = y; this.step = step; } } public static void main(String[] args) { Scanner cin = new Scanner(System.in); char a[][]; int vis[][]; int n = cin.nextInt(); a = new char[n + 5][n + 5]; vis = new int[n + 5][n + 5]; int tx = 0, ty = 0, sx = 0, sy = 0, dx = 0, dy = 0; int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}}; for (int i = 0; i < n; i++) { String s = cin.next(); for (int j = 0; j < n; j++) { a[i][j] = s.charAt(j); if(a[i][j] == 'S') { sx = i; sy = j; } if(a[i][j] == 'T') { tx = i; ty = j; } if(a[i][j] == 'L') { dx = i; dy = j; } } } Queue<Node>q = new LinkedList<Node>(); q.add(new Node(sx, sy, 0)); int ans1 = 0, ans2 = 0; while(!q.isEmpty()) { Node node = q.poll(); if(node.x == dx && node.y == dy) { ans1 = node.step; break; } for(int i = 0;i < 4;i++) { int nx = node.x + dir[i][0]; int ny = node.y + dir[i][1]; if(nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] == '#' || vis[nx][ny] == 1)continue; vis[nx][ny] = 1; q.add(new Node(nx, ny, node.step + 1)); } } q.clear(); for(int i = 0;i < n;i++) for(int j = 0;j < n;j++)vis[i][j] = 0; q.add(new Node(tx, ty, 0)); while(!q.isEmpty()) { Node node = q.poll(); if(node.x == dx && node.y == dy) { ans2 = node.step; break; } for(int i = 0;i < 4;i++) { int nx = node.x + dir[i][0]; int ny = node.y + dir[i][1]; if(nx < 0 || nx >= n || ny < 0 || ny >= n || a[nx][ny] == '#' || vis[nx][ny] == 1)continue; vis[nx][ny] = 1; q.add(new Node(nx, ny, node.step + 1)); } //System.out.println(node.x + " " + node.y); } System.out.println(ans1 + ans2); } }