Codeforces Round #542 C. Connect 搜索
Alice lives on a flat planet that can be modeled as a square grid of size water.
Alice resides in land cell (r2,c2) . At any moment, she may move to one of the cells adjacent to where she is—in one of the four directions (i.e., up, down, left, or right).
Unfortunately, Alice cannot swim, and there is no viable transportation means other than by foot (i.e., she can walk only on land). As a result, Alice's trip may be impossible.
To help Alice, you plan to create at most one tunnel between some two land cells. The tunnel will allow Alice to freely travel between the two endpoints. Indeed, creating a tunnel is a lot of effort: the cost of creating a tunnel between cells (rs−rt)2+(cs−ct)2 .
For now, your task is to find the minimum possible cost of creating at most one tunnel so that Alice could travel from 0 .
The first line contains one integer 1≤n≤50 ) — the width of the square grid.
The second line contains two space-separated integers 1≤r1,c1≤n ) — denoting the cell where Alice resides.
The third line contains two space-separated integers 1≤r2,c2≤n ) — denoting the cell to which Alice wishes to travel.
Each of the following water.
It is guaranteed that land.
Print an integer that is the minimum possible cost of creating at most one tunnel so that Alice could travel from (r2,c2) .
5 1 1 5 5 00001 11111 00111 00110 00110
10
3 1 3 3 1 010 101 010
8
In the first sample, a tunnel between cells (5,5) .
In the second sample, clearly a tunnel between cells (1−3)2+(3−1)2=8 .
就是简单的搜索，用dfs求出连通块，然后就遍历起点的所有连通块到终点的连通块，求出最短距离。
#include <cstring> #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn = 2550; char s[60][60]; int n, sx, sy, gx, gy,ans=inf; int dx[4] = { 0,1,-1,0 }; int dy[4] = { 1,0,0,-1 }; bool vis[60][60]; struct node { int x, y; node(int x = 0, int y = 0) :x(x), y(y) {} }; int cnt = 0; void dfs(int x, int y, node *d) { for (int i = 0; i < 4; i++) { int tx = x + dx[i]; int ty = y + dy[i]; if (vis[tx][ty]) continue; if (s[tx][ty] == '1') continue; if (tx<1 || ty<1 || tx>n || ty>n) continue; vis[tx][ty] = true; d[cnt++] = node(tx, ty); dfs(tx, ty, d); } } int min_(int a,int b) { return a < b ? a : b; } int main() { cin >> n >> sx >> sy >> gx >> gy; for (int i = 1; i <= n; i++) cin >> s[i] + 1; node a[maxn], b[maxn]; a[0] = node(sx, sy); b[0] = node(gx, gy); vis[sx][sy] = true;cnt = 1; dfs(sx, sy, a); if(vis[gx][gy]) { printf("0 "); return 0; } int tot = cnt;cnt = 1; vis[gx][gy] = 1; dfs(gx, gy, b); //printf("%d %d ", cnt, tot); for(int i=0;i<tot;i++) { for(int j=0;j<cnt;j++) { //printf("%d %d %d %d ", a[i].x, a[i].y, b[j].x, b[j].y); int exa = (a[i].x - b[j].x)*(a[i].x - b[j].x) + (a[i].y - b[j].y)*(a[i].y - b[j].y); //printf("%d ", exa); ans = min_(ans, exa); } } printf("%d ", ans); return 0; }