2012-12-01 19:07:54Morris
[ZJ][BFS] d373. 5. 乳酪的誘惑
內容 ：
這個問題跟傳統的老鼠走迷宮問題不太一樣，給定一個四方形的格點空間
x 座標與y 座標由左下角原點以0 開始往右和往上遞增，裡面有一個區域是鼠窩，另外有一個區域是乳酪屋
此外還有很多障礙物是用來阻擋鼠輩的橫行，也就是障礙物是不可穿越的。
在此空間裡可能沒有路可以從鼠窩走到乳酪屋，此種情況你必須回報沒有路徑
如果有路可以連接鼠窩跟乳酪屋的話，你必須算出從鼠窩走到乳酪屋的最短路徑。
老鼠的每一步只能往四個方向走:上、下、左、右，不能走對角方向。出發點與終點可以是鼠窩與乳酪屋的任何一個位置。
以圖一為例，鼠窩到乳酪屋的最短距離為15，由鼠窩裡圓圈所標示的點(10,2)往左出發走到乳酪屋中圓圈所標示的點(1,8)。
鼠窩與乳酪屋的形狀一定是一條直線，障礙物可以是一點可以是一條直線也可以是一個矩形區域
圖一中的障礙物是由三個點與兩條直線所構成，分別為點(2,6)、(3,5)、與(4,4)和線(4,3)~(7,3)與(7,4)~(7,9)。
在找尋最短路徑時，不要只派遣一隻老鼠出任務，這樣會累死這隻可憐的倒霉鼠的。
輸入說明
：
輸入的第一行為兩個整數，描述方形格點空間的大小，第一個表示行的數目，第二個表示列的數目
在此問題中行和列的數目都不會超過1000 (<=1000)。
接下來“.mb”表示後面用兩點來描述鼠窩的位置，每個點先x 座標再y 座標，兩個點沒有固定的先後排序。
接下來“.cb”表示後面用兩點來描述乳酪屋的位置，兩個點也沒有固定的先後排序。
最後“.bb”表示後面開始每一行描述一個障礙物的位置，不管是一點還是一條線都是用兩點來表示
最後以“.be”表示結束。
輸出說明
：
沒有路徑的話，輸出“no path”。有路徑的話輸出最短路徑距離。
範例輸入 ：
以圖一為例，其輸入檔案如下: 14 10 .mb 10 4 10 1 .cb 1 8 4 8 .bb 2 6 2 6 3 5 3 5 4 4 4 4 4 3 7 3 7 9 7 4 .be
範例輸出 ：
15
提示
：
出處
：
97全國能力縣賽
(管理：pcshic)
以前寫了好久都沒過，這次回頭寫一次 BFS 通過
#include <stdio.h>
#include <queue>
using namespace std;
char g[1000][1000] = {};
int dis[1000][1000] = {};
int n, m, ax, ay, bx, by, tmp;
int i, j, k;
void color(int c, int ax, int ay, int bx, int by) {
if(ax > bx) tmp = ax, ax = bx, bx = tmp;
if(ay > by) tmp = ay, ay = by, by = tmp;
int i, j;
for(i = ax; i <= bx; i++)
for(j = ay; j <= by; j++)
g[i][j] = c;
}
struct Pt {
int x, y;
};
void solve() {
queue<Pt> Q;
Pt p, tn;
int tx, ty;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
if(g[i][j] == 1) {
p.x = i, p.y = j;
Q.push(p);
dis[i][j] = 1;
}
int ans = 0xfffff;
while(!Q.empty()) {
tn = Q.front();
Q.pop();
for(i = 0; i < 4; i++) {
tx = tn.x + dir[i][0], ty = tn.y + dir[i][1];
if(tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if(dis[tx][ty] == 0 && g[tx][ty] != 3) {
dis[tx][ty] = dis[tn.x][tn.y]+1;
if(g[tx][ty] == 2 && dis[tx][ty] < ans)
ans = dis[tx][ty];
p.x = tx, p.y = ty;
Q.push(p);
}
}
}
if(ans == 0xfffff)
puts("no path");
else
printf("%d\n", ans-1);
}
int main() {
scanf("%d %d", &n, &m);
scanf("%*s %d %d %d %d", &ax, &ay, &bx, &by);
color(1, ax, ay, bx, by);
scanf("%*s %d %d %d %d", &ax, &ay, &bx, &by);
color(2, ax, ay, bx, by);
char cmd[20];
gets(cmd);
gets(cmd);
while(gets(cmd)) {
if(cmd[0] == '.') break;
sscanf(cmd, "%d %d %d %d", &ax, &ay, &bx, &by);
color(3, ax, ay, bx, by);
}
solve();
return 0;
}
以前寫了好久都沒過，這次回頭寫一次 BFS 通過
#include <stdio.h>
#include <queue>
using namespace std;
char g[1000][1000] = {};
int dis[1000][1000] = {};
int n, m, ax, ay, bx, by, tmp;
int i, j, k;
void color(int c, int ax, int ay, int bx, int by) {
if(ax > bx) tmp = ax, ax = bx, bx = tmp;
if(ay > by) tmp = ay, ay = by, by = tmp;
int i, j;
for(i = ax; i <= bx; i++)
for(j = ay; j <= by; j++)
g[i][j] = c;
}
struct Pt {
int x, y;
};
void solve() {
queue<Pt> Q;
Pt p, tn;
int tx, ty;
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
if(g[i][j] == 1) {
p.x = i, p.y = j;
Q.push(p);
dis[i][j] = 1;
}
int ans = 0xfffff;
while(!Q.empty()) {
tn = Q.front();
Q.pop();
for(i = 0; i < 4; i++) {
tx = tn.x + dir[i][0], ty = tn.y + dir[i][1];
if(tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
if(dis[tx][ty] == 0 && g[tx][ty] != 3) {
dis[tx][ty] = dis[tn.x][tn.y]+1;
if(g[tx][ty] == 2 && dis[tx][ty] < ans)
ans = dis[tx][ty];
p.x = tx, p.y = ty;
Q.push(p);
}
}
}
if(ans == 0xfffff)
puts("no path");
else
printf("%d\n", ans-1);
}
int main() {
scanf("%d %d", &n, &m);
scanf("%*s %d %d %d %d", &ax, &ay, &bx, &by);
color(1, ax, ay, bx, by);
scanf("%*s %d %d %d %d", &ax, &ay, &bx, &by);
color(2, ax, ay, bx, by);
char cmd[20];
gets(cmd);
gets(cmd);
while(gets(cmd)) {
if(cmd[0] == '.') break;
sscanf(cmd, "%d %d %d %d", &ax, &ay, &bx, &by);
color(3, ax, ay, bx, by);
}
solve();
return 0;
}