#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
typedef struct
{
int r;
int c;
int step;
}LOC;//點(diǎn)的屬性
typedef struct
{
int sr, sc, er, ec;
}POR;//傳送門的屬性
char buf[1000];
char map[101][101];//地圖
int N, M, W;
queue<LOC> Q;//點(diǎn)的隊(duì)列
vector<POR> P;//存儲(chǔ)所有的傳送門信息
int sr, sc, er, ec;//start, end, row, col
int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//代表四個(gè)方向
void addLOC(int r, int c, int step)
{
LOC tmp;
tmp.c = c;
tmp.r = r;
tmp.step = step;
Q.push(tmp);
map[r][c] = '2';
}//在隊(duì)列中添加一個(gè)點(diǎn)唉匾,并在地圖上留下標(biāo)記‘2’孕讳,防止重復(fù)(0表示可以走,1表示墻巍膘,2表示走過(guò))
void solve()
{
int i;
addLOC(sr, sc, 0);//添加第一個(gè)點(diǎn)(起點(diǎn))
here:
while(!Q.empty())
{
LOC cur = Q.front();//提取這個(gè)點(diǎn)的信息
Q.pop();//處理后便可以退出隊(duì)列
if(cur.c == ec && cur.r == er)
{
cout << cur.step << endl;
return;
}//如果到達(dá)終點(diǎn)厂财,就輸出當(dāng)前的步數(shù)
for(i = 0; i < W; ++i)
{
if(P[i].sr == cur.r && P[i].sc == cur.c)
{
if(map[P[i].er][P[i].ec] == '0')
addLOC(P[i].er, P[i].ec, cur.step+1);
goto here;
}
}//遍歷傳送門,如果踩到了峡懈,而且傳送到的地方不是墻也沒(méi)有走過(guò)璃饱,就添加這個(gè)點(diǎn),繼續(xù)看隊(duì)列中的下一個(gè)點(diǎn)
//否則此路不通肪康,看隊(duì)列中的下一個(gè)點(diǎn)
int tmpr, tmpc, i;
for(i = 0; i < 4; ++i)
{
tmpr = cur.r+dir[i][0];
tmpc = cur.c+dir[i][1];
if(tmpr>=0 && tmpr<N && tmpc>=0 && tmpc<M && map[tmpr][tmpc]=='0')
{
addLOC(tmpr, tmpc, cur.step+1);
}
}//嘗試四個(gè)方向荚恶,如果某個(gè)方向有路(不是墻也沒(méi)有到地圖外也沒(méi)有走過(guò)),就添加這個(gè)點(diǎn)
}
cout << "die" << endl;//如果一直都沒(méi)有return磷支,輸出die
}
//廣度優(yōu)先搜索谒撼,使用隊(duì)列實(shí)現(xiàn)
int main()
{
//freopen("data.txt", "r", stdin);
int num, i;
cin >> num;
while(num--)
{
P.clear();//把上一個(gè)case的陷阱信息置空
while(!Q.empty())
Q.pop();//把上一個(gè)case的點(diǎn)的隊(duì)列置空置空
cin >> N >> M;//輸入行和列數(shù)
gets(buf);//吃掉回車
for(i = 0; i < N; ++i)
gets(map[i]);//讀入地圖
cin >> W;//傳送門個(gè)數(shù)
for(i = 0; i < W; ++i)
{
POR tmp;
cin >> tmp.sr >> tmp.sc >> tmp.er >> tmp.ec;
P.push_back(tmp);
}//讀入傳送門并把它加入數(shù)組
cin >> sr >> sc >> er >> ec;//輸入起點(diǎn)和終點(diǎn)的行,列
solve();//調(diào)用函數(shù)解決迷宮
}
return 0;
}
solve()函數(shù)采用深度優(yōu)先搜索算法雾狈,遍歷離當(dāng)前點(diǎn)最近的點(diǎn)(或傳送門到達(dá)的點(diǎn))加入隊(duì)列廓潜,被加入的點(diǎn)在與“推出它的點(diǎn)”同步數(shù)的點(diǎn)被處理完之前都不會(huì)被處理,換句話說(shuō)善榛,處理一個(gè)點(diǎn)過(guò)后可能會(huì)在隊(duì)尾加入數(shù)個(gè)點(diǎn)(也可能不加入)辩蛋,加入后需要做的是繼續(xù)提取隊(duì)頭的點(diǎn)進(jìn)行操作。廣度優(yōu)先可以想象為河流的分流過(guò)程锭弊。