11515: 【原1515】采购
题目
题目描述
author: USACO 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1515
Description
skytim是伟大帝国UDF的首脑。作为一国的领袖，skytim很早就认识到一国的交通对经济建设的重要性。于是他要求UDF国内的建筑排成m*n的网络，道路建设在建筑的上方，并且每条道路都连接着两个有公共边的建筑。如下图所示：
这天是UDF国建国110周年纪念日，skytim正在主持盛大的阅兵式。随着“同志们好！”“首长好！”的声响此起彼伏，skytim的手机突然响了，是他的夫人Cyning打来的。
“skytim你早饭煮烂了，快给我回来！”
“啊？我还在阅兵呢！”
“我不管你现在在哪里，现在马上给我回来！”
“嗯，我现在马上回去！”
“回来记得顺路帮我买一把油纸伞。我要撑着它走过那条雨巷。好想知道成为戴望舒笔下那个丁香一样的结着愁怨的姑娘是一种怎样的体验。”
“行行行，随你。”
为了及时完成夫人的任务，skytim希望能够走一条最短的经过伞店的路径回家。但遗憾的是有些建筑正在施工，和它连着的道路都不能走。好在skytim早就对自己国家的地图烂熟于心，请你协助他找到最短的路径。
Input Format
输入第一行有两个整数n,m，表示地图的规模。
接下来m行每行n个数字，表示该建筑的状态。其中：
- 0表示普通建筑，可以经过。
- 1表示正在施工中的建筑，不可以经过。
- 2表示skytim阅兵的位置。
- 3表示skytim和Cyning的家。
- 4表示伞店。
Output Format
输出一个整数，表示skytim最少需要移动的距离。
Sample Input
8 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0
Sample Output
11
Limits
对于40%的数据，1≤ n,m≤ 10;
对于100%的数据，1≤ n,m≤ 1000.
Hints
skytim在买伞的过程中可以先经过家。
ligongzzz's solution
//Written by LCK
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int m, n;
int ans = 1e6;
int map[1000][1000] = { 0 };
int sx, sy, ex, ey;
int step[1000][1000] = { 0 };
int a[1000000] = { 0 }, b[1000000] = { 0 };
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int cnt = -1;
class node {
public:
int x;
int y;
};
class shop {
public:
int x;
int y;
} sh[1000000] = { 0,0 };
void bfs(node s) {
queue<node> que;
que.push(s);
node nw, nxt;
while (!que.empty()) {
nw = que.front();
que.pop();
for (int i = 0; i < 4; ++i) {
nxt.x = nw.x + dx[i];
nxt.y = nw.y + dy[i];
if (nxt.x >= 0 && nxt.x < m&&nxt.y >= 0 && nxt.y < n&&step[nxt.x][nxt.y] == 0 && map[nxt.x][nxt.y] != 1) {
step[nxt.x][nxt.y] = step[nw.x][nw.y] + 1;
que.push(nxt);
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
cin >> map[i][j];
if (map[i][j] == 2) { sx = i; sy = j; }
if (map[i][j] == 3) { ex = i; ey = j; }
if (map[i][j] == 4) {
cnt++;
sh[cnt].x = i;
sh[cnt].y = j;
}
}
node s = { sx,sy };
bfs(s);
for (int i = 0; i <= cnt; ++i) {
a[i] = step[sh[i].x][sh[i].y];
}
memset(step, 0, sizeof(step));
node e = { ex,ey };
bfs(e);
for (int i = 0; i <= cnt; ++i) {
b[i] = step[sh[i].x][sh[i].y];
}
int tmp;
for (int i = 0; i <= cnt; ++i) {
if (a[i] > 0 && b[i] > 0) {
tmp = a[i] + b[i];
ans = min(ans, tmp);
}
}
cout << ans;
return 0;
}
Neight99's solution
#include <iostream>
using namespace std;
int **city, **skytim, **home, m, n;
int main() {
int **city, **skytim, **home, a = 0, b = 0;
cin >> n >> m;
int less = m * n;
city = new int *[m + 2];
skytim = new int *[m + 2];
home = new int *[m + 2];
for (int i = 0; i < m + 2; i++) {
city[i] = new int[n + 2];
skytim[i] = new int[n + 2];
home[i] = new int[n + 2];
}
for (int i = 0; i < m + 2; i++) {
city[i][0] = skytim[i][0] = home[i][0] = -10;
city[i][n + 1] = skytim[i][n + 1] = home[i][n + 1] = -10;
}
for (int i = 0; i < n + 2; i++) {
city[0][i] = skytim[0][i] = home[0][i] = -10;
city[m + 1][i] = skytim[m + 1][i] = home[m + 1][i] = -10;
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
cin >> city[i][j];
if (city[i][j] == 1) {
skytim[i][j] = -2;
home[i][j] = -2;
} else if (city[i][j] == 2) {
skytim[i][j] = 0;
home[i][j] = -1;
b++;
} else if (city[i][j] == 3) {
home[i][j] = 0;
skytim[i][j] = -1;
a++;
} else {
skytim[i][j] = -1;
home[i][j] = -1;
a++;
b++;
}
}
}
int N = 0;
while (a != 0) {
bool key = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (skytim[i][j] == N) {
if (skytim[i - 1][j] == -1) {
skytim[i - 1][j] = N + 1;
a--;
key = 0;
}
if (skytim[i + 1][j] == -1) {
skytim[i + 1][j] = N + 1;
a--;
key = 0;
}
if (skytim[i][j - 1] == -1) {
skytim[i][j - 1] = N + 1;
a--;
key = 0;
}
if (skytim[i][j + 1] == -1) {
skytim[i][j + 1] = N + 1;
a--;
key = 0;
}
}
}
}
if (key == 1) {
break;
}
N++;
}
N = 0;
while (b != 0) {
bool key = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (home[i][j] == N) {
if (home[i - 1][j] == -1) {
home[i - 1][j] = N + 1;
b--;
key = 0;
}
if (home[i + 1][j] == -1) {
home[i + 1][j] = N + 1;
b--;
key = 0;
}
if (home[i][j - 1] == -1) {
home[i][j - 1] = N + 1;
b--;
key = 0;
}
if (home[i][j + 1] == -1) {
home[i][j + 1] = N + 1;
b--;
key = 0;
}
}
}
}
if (key == 1) {
break;
}
N++;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (city[i][j] == 4 && home[i][j] >= 1 && skytim[i][j] >= 1) {
int tmp = home[i][j] + skytim[i][j];
less = (tmp < less) ? tmp : less;
}
}
}
cout << less;
}
yyong119's solution
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node {
node(int a, int b, int p) {
x = a; y = b; step = p;
};
int x, y, step;
};
const int MAX_N = 1001;
const int movement[4][2] = { { -1, 0 },{ 1, 0 },{ 0, -1 },{ 0, 1 } };
int map[MAX_N][MAX_N], map1[MAX_N][MAX_N], map2[MAX_N][MAX_N];
bool isVisited[MAX_N][MAX_N];
int main() {
int n, m, mincost = 0xFFFFFF;
int sx, sy, ex, ey;
queue<node> umb;
cin >> n >> m;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) {
cin >> map[i][j];
if (map[i][j] == 4) umb.push(node(i, j, 0));
else if (map[i][j] == 2) { sx = i; sy = j; }
else if (map[i][j] == 3) { ex = i; ey = j; }
}
queue<node> que; que.push(node(sx, sy, 0)); isVisited[sx][sy] = true;
while (!que.empty()) {
node now = que.front();
for (int i = 0; i < 4; ++i) {
node next(now.x + movement[i][0], now.y + movement[i][1], now.step + 1);
if (next.x < 1 || next.x > m || next.y < 1 || next.y > n) continue;
if (map[next.x][next.y] != 1 && !isVisited[next.x][next.y]) {
que.push(next);
isVisited[next.x][next.y] = true;
map1[next.x][next.y] = next.step;
}
}
que.pop();
}
memset(isVisited, false, sizeof(isVisited));
que.push(node(ex, ey, 0)); isVisited[ex][ey] = true;
while (!que.empty()) {
node now = que.front();
for (int i = 0; i < 4; ++i) {
node next(now.x + movement[i][0], now.y + movement[i][1], now.step + 1);
if (next.x < 1 || next.x > m || next.y < 1 || next.y > n) continue;
if (map[next.x][next.y] != 1 && !isVisited[next.x][next.y]) {
que.push(next);
isVisited[next.x][next.y] = true;
map2[next.x][next.y] = next.step;
}
}
que.pop();
}
while (!umb.empty()) {
node tmp = umb.front(); umb.pop();
if (map1[tmp.x][tmp.y] + map2[tmp.x][tmp.y] < mincost && map1[tmp.x][tmp.y] + map2[tmp.x][tmp.y])
mincost = map1[tmp.x][tmp.y] + map2[tmp.x][tmp.y];
}
cout << mincost << endl;
return 0;
}