【HDOJ】2612 Find a way

BFS。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; #define INF 0x3fffffff typedef struct node_st {
int x, y, s;
node_st() {}
node_st(int xx, int yy, int ss) {
x = xx; y = yy; s = ss;
}
} node_st; char visit[][];
char map[][];
int step[][][];
int n, m;
int direct[][] = {{-,},{,},{,-},{,}}; void bfs(int x, int y, int sel) {
int i, s;
queue<node_st> que;
node_st node; memset(visit, , sizeof(visit));
memset(step[sel], , sizeof(step[sel]));
visit[x][y] = ;
que.push(node_st(x,y,)); while ( !que.empty() ) {
node = que.front();
que.pop();
s = node.s + ;
for (i=; i<; ++i) {
x = node.x + direct[i][];
y = node.y + direct[i][];
if (x< || x>=n || y< || y>=m)
continue;
if (visit[x][y])
continue;
visit[x][y] = ;
if (map[x][y] == '#')
continue;
if (map[x][y] == '@')
step[sel][x][y] = s;
que.push(node_st(x,y,s));
}
}
} int main() {
int i, j, tmp, min;
int yx, yy, mx, my; while (scanf("%d %d%*c", &n, &m) != EOF) {
for (i=; i<n; ++i) {
scanf("%s", map[i]);
for (j=; j<m; ++j) {
if (map[i][j] == 'Y') {
yx = i;
yy = j;
} else if (map[i][j] == 'M') {
mx = i;
my = j;
}
}
}
bfs(yx, yy, );
bfs(mx, my, );
min = INF;
for (i=; i<n; ++i) {
for (j=; j<m; ++j) {
if (step[][i][j] && step[][i][j]) {
tmp = step[][i][j] + step[][i][j];
if (tmp < min)
min = tmp;
}
}
}
printf("%d\n", min*);
} return ;
}
上一篇:HTTP 错误 500.21 - Internal Server Error 处理程序“ExtensionlessUrlHandler-ISAPI-4.0_64bit”在其模块列表中有一个错误模块“IsapiModule” 解决方法


下一篇:Leecode刷题之旅-C语言/python-326 3的幂