ZeroJudge D406: Flowing Water

Water flows from top to bottom. Now you're given a map of the pipes between them. Water can flow downwards, to the right, or the left.

But sometimes, it can flow upwards too. Now, starting from the top of the map, please output the time it reaches.

※ There is only one starting point, and it is located in the first row.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF input, the first line of each test case contains a number S, where S = 2 means water cannot flow upwards, and S = 1 means water can flow upwards.
The second line contains two numbers N and M, where N represents the number of subsequent rows, and M represents the number of numbers in each row. (1 ≤ N, M ≤ 100)
Then there will be N rows, each containing M numbers, where 1 indicates there is a pipe, and 0 indicates there is no pipe.		For each location, output the time it takes to reach that location.
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 Sample Input/Output

Thought Process

Declare a Vector<Vector> ans and initialize all values to 0. Use BFS. The returned data can include a Count variable representing time. Each time you reach a point, set the current Count in the ans at the current position. Every time you call BFS again, Count should be incremented by 1.

Once a point has been traversed, it cannot be traversed again. You can use a Map to check if the next starting point has already been visited.

Sample Code－ZeroJudge D406: Flowing Water

#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
Tags

Related Posts

Comments