题目链接:http://codeforces.com/contest/1130/problem/C
题意是给了一个n*n的地图,然后给了起点和终点的坐标,其中地图中陆地为0,水面为1。有一个人只能走陆地,他想从起点走到终点,他可以在任意两个陆地之间建一座桥(只能建一座桥),花费为欧几里得距离,问他从起点到终点的最小花费为多少(如果不用建桥就是0)。
思路是因为n的数据范围很小,所以我们可以将与起点连通的陆地和与终点连通的陆地标记出来,然后n^4暴力,更新一个最小值就好了,再特判一下不用建桥的情况。
AC代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
char str[55][55];
int pre[55][55];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
struct Node{
int x,y;
}Now,Next,S;
int x,y,s,e;
int pos;
bool vis[55][55];
int xx,yy;
bool Check(int _x,int _y){
if(str[_x][_y]=='0'&&_x>=1&&_y>=1&&_x<=n&&_y<=n&&vis[_x][_y]==false)return true;
return false;
}
bool bfs(int xxx,int yyy,int pos){
queue<Node> q;
memset(vis,false,sizeof(vis));
S.x = xxx;
S.y = yyy;
pre[xxx][yyy] = pos;
q.push(S);
while(!q.empty()){
Now = q.front();
q.pop();
for(int i=0;i<4;i++){
Next.x = Now.x + dir[i][0];
Next.y = Now.y + dir[i][1];
if(Check(Next.x, Next.y)){
vis[Next.x][Next.y] = true;
pre[Next.x][Next.y] = pos;
q.push(Next);
}
}
}
}
int main()
{
cin>>n;
cin>>x>>y>>s>>e;
for(int i=1;i<=n;i++){
scanf("%s",str[i] + 1);
}
bfs(x, y, 1);
if(pre[s][e] == 1){
puts("0");
return 0;
}
bfs(s, e, 2);
int ans = 0x3f3f3f3f;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int l=1;l<=n;l++){
for(int k=1;k<=n;k++){
if(pre[i][j] == 1 && pre[l][k] == 2){
ans = min(ans, (l - i) * (l - i) + (k - j) * (k - j));
}
}
}
}
}
cout<<ans<<endl;
return 0;
}