[ZJ][BFS] d373. 5. 乳酪的誘惑＠Morris' Blog

2012-12-01 19:07:54| 人氣1,713| 回應0 | 上一篇 | 下一篇

[ZJ][BFS] d373. 5. 乳酪的誘惑

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

這個問題跟傳統的老鼠走迷宮問題不太一樣，給定一個四方形的格點空間

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

範例輸出：

提示：

出處：

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;
}

我要檢舉

#d373#5. 乳酪的誘惑

台長： Morris

您可能對以下文章有興趣

b113. 6. 線性系統求解

[ZJ][二分+凸包計算面積] b221. 6. 耕者有其田

[ZJ][DP] a365. 3. 新井字遊戲

d887. 1.山脈種類(chain)

人氣(1,713) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][一年後修正版][樹型DP] b174. 旅游规划
此分類上一篇:[ZJ] d229. IOI研習營模考2-4砝碼

回應(0)