首页 > 代码库 > BZOJ1671 [Usaco2005 Dec]Knights of Ni 骑士
BZOJ1671 [Usaco2005 Dec]Knights of Ni 骑士
打水题啊打水题。。。然后就被虐了。。。
看不懂题目，后来查hzwer的blog，发现时题目翻译错了。。。我去我就说我的语文怎么这么差。
hzwer："总之就是在地图上从2出发，走到3，途中要至少经过一个4。"
原来如此，不就是两次bfs嘛。。。只是第一次bfs的时候要注意不能经过4。
然后开始bfs，在快要写死的时候。。。终于对了。。。
哈哈，status第六哦~~~不错不错
1 /************************************************************** 2 Problem: 1671 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:168 ms 7 Memory:16548 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 const int inf = (int) 1e9;15 const int dx[4] = {0, 0, -1, 1};16 const int dy[4] = {1, -1, 0, 0};17 18 struct QUEUE{19 int x, y;20 }q[500005];21 int d[2][1005][1005], mp[1005][1005];22 int n, m, sx[2], sy[2];23 24 inline int read(){25 int x = 0, sgn = 1;26 char ch = getchar();27 while (ch < ‘0‘ || ch > ‘9‘){28 if (ch == ‘-‘) sgn = -1;29 ch = getchar();30 }31 while (ch >= ‘0‘ && ch <= ‘9‘){32 x = x * 10 + ch - ‘0‘;33 ch = getchar();34 }35 return sgn * x;36 }37 38 inline bool check(int x, int y){39 return x < 1 || y < 1 || x > n || y > m;40 }41 42 void bfs(int p){43 q[0].x = sx[p], q[0].y = sy[p], d[p][sx[p]][sy[p]] = 0;44 int x, y, X, Y;45 for (int l = 0, r = 0; l <= r; ++l){46 X = q[l].x, Y = q[l].y;47 for (int i = 0; i < 4; ++i){48 x = X + dx[i], y = Y + dy[i];49 if (check(x, y) || mp[x][y] == 1 || d[p][x][y] != -1) continue;50 ++r;51 q[r].x = x, q[r].y = y;52 d[p][x][y] = d[p][X][Y] + 1;53 }54 }55 }56 57 int getans(){58 int res = inf;59 for (int i = 1; i <= n; ++i)60 for (int j = 1; j <= m; ++ j){61 if (d[0][i][j] == -1 || d[1][i][j] == -1 || mp[i][j] != 4) continue;62 res = min(res, d[0][i][j] + d[1][i][j]);63 }64 return res;65 }66 67 int main(){68 m = read(), n = read();69 for (int i = 1; i <= n; ++i)70 for (int j = 1; j <= m; ++j){71 d[0][i][j] = d[1][i][j] = -1;72 mp[i][j] = read();73 if (mp[i][j] == 2)74 sx[0] = i, sy[0] = j;75 if (mp[i][j] == 3)76 sx[1] = i, sy[1] = j;77 }78 79 bfs(0); bfs(1);80 printf("%d\n", getans());81 return 0;82 }
BZOJ1671 [Usaco2005 Dec]Knights of Ni 骑士
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。