传送门

题目描述
用一个n * n的矩阵表示一个岛屿，岛屿中有陆地和水域，陆地用0表示，水域用1表示，你只能在陆地上行走，在陆地上行走不需要花费任何费用，给定起点的坐标(sx，sy)与终点坐标（ex，ey），保证这两个点必定是陆地。
你可以在任意两块陆地上建立一个传送门且最多只能建一个传送门，传送门可以使两个点互达，费用是两点间横坐标、纵坐标的差的平方和，即(sx-ex)^2+(sy-ey)^2。
求从起点起到终点的最小花费，若不需要建传送门可直接到达终点则花费为0。

输入
有多组测试数据。
第一行输入一个正整数t(2≤t≤10)，表示测试数据的组数。
对于第组测试数据输入如下：
第一行输入一个正整数n(1≤n≤100)。
第二行输入起点坐标sx,sy。
第三行输入终点坐标ex,ey。
接下来的n行输入一个n * n 的01矩阵，0与1之间无空格，详见样例。
输出
对于每组测试数据输出一行，即一个整数表示该组数据的最小花费。

样例输入
3
5
1 1
5 5
00001
11111
00111
00110
00110
3
1 3
3 1
010
101
010
2
1 1
2 2
00
10

样例输出
10
8
0

题解：先从起点开始dfs一遍看是否能到达终点，在搜索的过程中保存陆地坐标，然后从终点开始dfs一遍，保存陆地坐标，最后暴力找满足条件的最小的距离。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 10;
int mp[maxn][maxn];
int t;
int n;
int sx,sy;
int ex,ey;
int f;
int ans;
int dir[4][2] = {{-1, 0},{1, 0},{0, 1},{0, -1}};
int a[100000][2];
int b[100000][2];
int p1, p2;

void init(){
  p1 = 0;
  p2 = 0;
  ans = 0x3f3f3f3f;
  for(int i = 1; i <= n; i ++)
   for(int j = 1; j <= n; j++)
     mp[i][j] = 0;
  f = 0;
}

int calc(int sx, int ex, int sy, int ey){
  return (sx - ex) * (sx - ex) + (sy - ey) * (sy - ey);
}

void dfsx(int x, int y){
  if(x == ex && y == ey){
    f = 1;
    return;
  }
  if(mp[x][y])  return;
  a[p1][0] = x; a[p1 ++][1] = y;
  mp[x][y] = 1;
  for(int i = 0; i <= 3; i ++){
    int dx = dir[i][0] + x;
    int dy = dir[i][1] + y;
    if(dx >= 1 && dx <= n && dy >= 1 && dy <= n)
        dfsx(dx, dy);
  }
}

void dfse(int x, int y){
  if(mp[x][y]) return;
  b[p2][0] = x; b[p2 ++][1] = y;
  mp[x][y] = 1;
  for(int i = 0; i <= 3; i ++){
    int dx = dir[i][0] + x;
    int dy = dir[i][1] + y;
    if(dx >= 1 && dx <= n && dy >= 1 && dy <= n)
      dfse(dx, dy);
    }
}

int main()
{
  scanf("%d",&t);
  while(t --){
    scanf("%d",&n);
    init();

    scanf("%d%d",&sx,&sy);
    scanf("%d%d",&ex,&ey);
    char c;
    for(int i = 1; i <= n; i ++)
      for(int j = 1; j <= n; j ++){
        cin >> c;
        mp[i][j] = c - '0';
      }

   dfsx(sx, sy);
   if(f){
     puts("0");
     continue;
   }
   dfse(ex, ey);

   for(int i = 0; i < p1; i ++)
    for(int j = 0; j < p2; j ++)
      ans = min(ans, calc(a[i][0], b[j][0], a[i][1], b[j][1]));

  printf("%d\n",ans);
  }
  return 0;
}