Codeforces 1130 Connect——水题

Codeforces 1130 Connect——水题

康复训练

#include using namespace std;const int maxn = 100;int n;int r1, c1, r2, c2;char str[maxn];int G[maxn][maxn];int tot;bool vis[maxn][maxn];typedef pair P;vector

vec[maxn*maxn];int s, t;const int dx[] = {-1, 1, 0, 0};const int dy[] = {0, 0, -1, 1};const int INF = 0x3f3f3f3f;void dfs(int x, int y) { vis[x][y] = 1; vec[tot].push_back(make_pair(x, y)); if (x == r1 && y == c1) { s = tot; } else if (x == r2 && y == c2) { t = tot; } for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (1 <= xx && xx <= n && 1 <= yy && yy <= n && G[xx][yy] == 0 && !vis[xx][yy]) { dfs(xx, yy); } }}int dis(int x1, int y1, int x2, int y2) { return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);}int main() { scanf("%d", &n); scanf("%d %d %d %d", &r1, &c1, &r2, &c2); getchar(); for (int i = 1; i <= n; i++) { gets(str); for (int j = 1; j <= n; j++) { G[i][j] = str[j-1] - '0'; } } if (r1 == r2 && c1 == c2) { printf("0\n"); return 0; } tot = 0; memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n * n; i++) { vec[i].clear(); } s = t = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (G[i][j] == 0 && !vis[i][j]) { ++tot; dfs(i, j); } } } if (s == t) { printf("0\n"); } else { int ans = INF; for (int i = 0; i < vec[s].size(); i++) { for (int j = 0; j < vec[t].size(); j++) { ans = min(ans, dis(vec[s][i].first, vec[s][i].second, vec[t][j].first, vec[t][j].second)); } } printf("%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。