# ZeroJudge d453. 最短距離
[d453. 最短距離 (題目連結)](https://zerojudge.tw/ShowProblem?problemid=d453)
<font color="#00CE17">**AC**</font> **(2ms, 344KB)**

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define x first
#define y second

int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin>>n;
	while(n--){
		int n, m, bx, by, ex, ey;
		cin>>n>>m>>bx>>by>>ex>>ey;
		int dx[4]={0, 0, 1, -1};
		int dy[4]={-1, 1, 0, 0};
		bx--, by--, ex--, ey--;
		int map[n][m];
		string data;
		for(int i=0; i<n; i++){
			cin>>data;
			for(int j=0; j<m; j++){
				map[i][j]=data[j]-'0';
			}
		}
		int sc[n][m];
		queue <pair<int, int>> q;
		q.push({bx, by});
		memset(sc, -1, sizeof(sc));
		sc[bx][by]=1;
		while(!q.empty()){
			pair<int, int> now;
			now=q.front();
			q.pop();
			for(int i=0; i<4; i++){
				int xx=now.x+dx[i], yy=now.y+dy[i];
				if(xx>=0 && xx<n && yy>=0 && yy<m){
					if(map[xx][yy]==0 && sc[xx][yy]==-1){
						q.push({xx, yy});
						sc[xx][yy]=sc[xx-dx[i]][yy-dy[i]]+1;
					}
				}
			}
		}
		if(sc[ex][ey]==-1) cout<<0<<'\n';
		else cout<<sc[ex][ey]<<'\n';
	}
	
	return 0;
}

###### 闕以諾 2022/7/20
###### tags: `C++` `ZeroJudge` `APCS`