ZeroJudge D406: 倒水時間

水由上而下的流，現在給你水管之間的地圖
水可以由上而下，可以往右流，往左流。

可是呢 … 有時候也可以往上流
現在從地圖的最上方開始倒水，請輸出到的時間。

※ 開始倒的地方只有 1 個且只在第一列倒

範例測資

範例輸入範例輸出
EOF 輸入，每組測資的第一列有一個數字 S，若 S = 2 代表水不能往上流， S = 1 代表水可以往上流。
第二列有兩個數字 N 和 M， N 代表接下來有 N 列，M代表每列上有多少數字。
( 1≦ N、M ≦ 100 )
接下來會有 N 列，每列上有 M 個數字， 1 代表有水管， 0 則代表沒有。		對每個地點輸出到的時間。
1
4 6
0 0 0 1 0 0
0 0 1 1 1 0
1 1 1 0 1 0
0 1 0 0 0 0
1
5 7
1 0 0 0 0 0 0
1 1 1 1 1 1 0
0 1 0 0 1 0 1
1 1 1 0 1 1 1
1 0 1 0 1 1 1
2
6 6
0 1 0 0 0 0
1 1 0 0 1 1
0 1 1 1 1 0
1 1 1 1 1 1
0 0 0 0 1 0
0 0 0 1 1 0		Case 1:
0 0 0 1 0 0
0 0 3 2 3 0
6 5 4 0 4 0
0 6 0 0 0 0
Case 2:
1 0 0 0 0 0 0
2 3 4 5 6 7 0
0 4 0 0 7 0 11
6 5 6 0 8 9 10
7 0 7 0 9 10 11
Case 3:
0 1 0 0 0 0
3 2 0 0 0 0
0 3 4 5 6 0
5 4 5 6 7 8
0 0 0 0 8 0
0 0 0 10 9 0
ZeroJudge D406 範例測資

解題思路

宣告一個 Vector<Vector<int>>ans 並且將所有數值預設為 0，使用 BFS，回傳的資料可以新增一個 Count 的變數，代表時間，每次跑到某一個點的時候就將目前的 Count 設定在目前走道的點的ans中。每一次重新呼叫 BFS 時 Count 都要 +1。

走過的點就不能再走了，可以使用 Map 來確認下次的起點是否有被走過。

範例程式碼－ZeroJudge D406: 倒水時間

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int S, N, M, locsize = 3;
vector<vector<int>>water, ans;
vector<pair<int, int>>loc;

pair<int, int> axis (int a, int b)
{
    pair<int, int>tmp;
    tmp.first = a;
    tmp.second = b;
    return tmp;
}

void BFS(vector<pair<int, int>>start, map<pair<int, int>, int>MAP, int count)
{
    if (start.size() == 0) return;
    vector<pair<int, int>>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        int y = start[i].first, x = start[i].second;
        ans[y][x] = count;
        MAP[start[i]]++;
        for (int j = 0; j<locsize; j++)
        {
            int yy = y + loc[j].first, xx = x + loc[j].second;
            if (yy >= 0 && yy < N && xx >= 0 && xx < M && water[yy][xx] == 1 && MAP[axis(yy, xx)] == 0) newStart.push_back(axis(yy, xx));
        }
    }
    BFS(newStart, MAP, count+1);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int count = 1;
    while (cin >> S >> N >> M)
    {
        loc.clear();
        loc.push_back(axis(1, 0));
        loc.push_back(axis(0, 1));
        loc.push_back(axis(0, -1));
        locsize = 3;
        water.clear();
        ans.clear();
        vector<pair<int, int>>start;
        for (int i = 0; i<N; i++)
        {
            vector<int>v;
            vector<int>hi;
            for (int j = 0; j<M; j++)
            {
                int tmp;
                cin >> tmp;
                if (i == 0 && tmp == 1) start.push_back(axis(i, j));
                v.push_back(tmp);
                hi.push_back(0);
            }
            water.push_back(v);
            ans.push_back(hi);
        }
        if (S == 1)
        {
            loc.push_back(axis(-1, 0));
            locsize++;
        }
        map<pair<int, int>, int>MAP;
        BFS(start, MAP, 1);
        cout << "Case " << count << ":\n";
        for (int i = 0; i<N; i++)
        {
            for (int j = 0; j<M; j++)
            {
                cout << ans[i][j] << " ";
            }
            cout << "\n";
        }
        count++;
    }
}

//ZeroJudge D406
//Dr. SeanXD
標籤

相關文章

發佈留言