我们可以使用 0-1 BFS 来解决这个问题。我们从左上角单元格开始，使用双端队列来存储当前单元格的坐标。每次从队列中取出一个单元格，我们会检查它的四个相邻单元格，如果相邻单元格是空单元格且没有被访问过，我们就将它加入队列，并更新它的距离。

如果相邻单元格是一个传送门，我们就将它加入队列的前面，并更新它的距离。我们还需要维护一个字典来存储每个传送门的位置，以便在使用传送门时能够快速找到它们。

我们还需要一个二维数组来存储每个单元格的距离，初始值为无穷大。我们将起点的距离设置为 0，然后开始 BFS。

在 BFS 的过程中，我们会检查每个单元格是否是终点，如果是，就返回它的距离。如果队列为空，说明无法到达终点，返回 -1。

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

classSolution:

defminMoves(self,matrix: List[str]) ->int:

m, n=len(matrix),len(matrix[0])

g= defaultdict(list)

for i, rowinenumerate(matrix):

for j, cinenumerate(row):

if c.isalpha():

g[c].append((i, j))

dirs= (-1,0,1,0,-1)

dist= [[inf]* nfor _inrange(m)]

dist[0][0]=0

q= deque([(0,0)])

while q:

i, j= q.popleft()

d= dist[i][j]

if i== m-1and j== n-1:

return d

c= matrix[i][j]

if cin g:

for x, yin g[c]:

if d< dist[x][y]:

dist[x][y]= d

q.appendleft((x, y))

del g[c]

for a, bin pairwise(dirs):

x, y= i+ a, j+ b

if (

0<= x< m

and0<= y< n

and matrix[x][y]!="#"

and d+1< dist[x][y]

):

dist[x][y]= d+1

q.append((x, y))

classSolution {

publicintminMoves(String[]matrix) {

int m= matrix.length, n= matrix[0].length();

Map<Character,List<int[]>> g=newHashMap<>();

for (int i=0; i< m; i++) {

String row= matrix[i];

for (int j=0; j< n; j++) {

char c= row.charAt(j);

if (Character.isAlphabetic(c)) {

g.computeIfAbsent(c, k->newArrayList<>()).add(newint[] {i, j});

}

}

}

int[] dirs= {-1,0,1,0,-1};

intINF=Integer.MAX_VALUE/2;

int[][] dist=newint[m][n];

for (int[] arr: dist)Arrays.fill(arr,INF);

dist[0][0]=0;

Deque<int[]> q=newArrayDeque<>();

q.add(newint[] {0,0});

while (!q.isEmpty()) {

int[] cur= q.pollFirst();

int i= cur[0], j= cur[1];

int d= dist[i][j];

if (i== m-1&& j== n-1)return d;

char c= matrix[i].charAt(j);

if (g.containsKey(c)) {

for (int[] pos: g.get(c)) {

int x= pos[0], y= pos[1];

if (d< dist[x][y]) {

dist[x][y]= d;

q.addFirst(newint[] {x, y});

}

}

g.remove(c);

}

for (int idx=0; idx<4; idx++) {

int a= dirs[idx], b= dirs[idx+1];

int x= i+ a, y= j+ b;

if (0<= x&& x< m&&0<= y&& y< n&& matrix[x].charAt(y)!='#'

&& d+1< dist[x][y]) {

dist[x][y]= d+1;

q.addLast(newint[] {x, y});

}

}

}

return-1;

}

}

classSolution {

public:

int minMoves(vector<string>& matrix) {

int m = matrix.size(), n = matrix[0].size();

unordered_map<char, vector<pair<int, int>>> g;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

char c = matrix[i][j];

if (isalpha(c)) g[c].push_back({i, j});

}

int dirs[5] = {-1, 0, 1, 0, -1};

int INF = numeric_limits<int>::max() / 2;

vector<vector<int>> dist(m, vector<int>(n, INF));

dist[0][0] = 0;

deque<pair<int, int>> q;

q.push_back({0, 0});

while (!q.empty()) {

auto[i, j] = q.front();

q.pop_front();

int d = dist[i][j];

if (i == m - 1 && j == n - 1) return d;

char c = matrix[i][j];

if (g.count(c)) {

for (auto[x, y] : g[c])

if (d < dist[x][y]) {

dist[x][y] = d;

q.push_front({x, y});

}

g.erase(c);

}

for (int idx = 0; idx < 4; ++idx) {

int x = i + dirs[idx], y = j + dirs[idx + 1];

if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] != '#' && d + 1 < dist[x][y]) {

dist[x][y] = d + 1;

q.push_back({x, y});

}

}

}

return -1;

}

};

function minMoves(matrix:string[]):number {

const m=matrix.length,

n=matrix[0].length;

const g=newMap<string, [number,number][]>();

for (let i=0;i<m;i++) {

for (let j=0;j<n;j++) {

const c=matrix[i][j];

if (/^[A-Za-z]$/.test(c)) {

if (!g.has(c))g.set(c, []);

g.get(c)!.push([i,j]);

}

}

}

const dirs= [-1,0,1,0,-1];

const INF=Number.MAX_SAFE_INTEGER;

const dist:number[][]=Array.from({ length:m }, ()=>Array(n).fill(INF));

dist[0][0]=0;

const cap=m*n*2+5;

const dq=newArray<[number,number]>(cap);

let l=cap>>1,

r=cap>>1;

const pushFront= (v: [number,number])=> {

dq[--l]=v;

};

const pushBack= (v: [number,number])=> {

dq[r++]=v;

};

const popFront= (): [number,number]=>dq[l++];

const empty= ()=>l===r;

pushBack([0,0]);

while (!empty()) {

const [i, j]=popFront();

const d=dist[i][j];

if (i===m-1&&j===n-1)returnd;

const c=matrix[i][j];

if (g.has(c)) {

for (const [x, y]ofg.get(c)!) {

if (d<dist[x][y]) {

dist[x][y]=d;

pushFront([x,y]);

}

}

g.delete(c);

}

for (let idx=0;idx<4;idx++) {

const x=i+dirs[idx],

y=j+dirs[idx+1];

if (0<=x&&x<m&&0<=y&&y<n&&matrix[x][y]!=='#'&&d+1<dist[x][y]) {

dist[x][y]=d+1;

pushBack([x,y]);

}

}

}

return-1;

}

<!-- tabs:end -->