# Untitled

unknown

plain_text

a year ago

5.5 kB

1

Indexable

Never

^{}

Pipe Network Our company has set up a pipe network for fuel distribution in factory. In that network, a fuel tank will be place at a location in the factory. From there, fuel will be distributed to other place by the pipe network. There are total 7 kinds of pipe, marked from 1-7 as below figures: Only the connected pipes can allow fuel pass through them. Two pipes are connected if they have a common end-point. For example : - In this case, fuel can flow from A to B - But in this case, fuel can not flow from A to B (Pipe in A does not have any common end-point with pipe in B) However, the pump used to distribute fuel has limit in its performance. Depend on its kind, the pump can only pump fuel as far as its limit. For example, let say the limit of pump is 3, that mean from start location, fuel can only flow to the farest place that 3 steps away (include start point). Given the map of pipe network, the location of the fuel tank (start position), the limit of pump, write a program to calculate the total number of pipes that fuel can flow to. Example 1: In this case, the height of the map (N) is 5, the length of of the map (M) is 6, location of the fuel tank is (2,1), the limit of the pump is 3 - First fuel is pumped to location (2,1) - Second, fuel flows to location (2,0) and (2,2) - Third, fuel flows to location (1,2) and (2,3) As the limit of pump is reached, the fuel can not flow any further. Hence, the total number of pipes that fuel can flow to is 5. Example 2: In this case, the height of the map (N) is 5, the length of of the map (M) is 6, location of the fuel tank is (2,2), the limit of the pump is 6. The answer is 15. [Constraints] - The fuel tank is alway placed at a location where a pipe exist [Input] - The number of test case T (T <= 50) - In each TC, the first row will give : + The size of the map N x M (5 <= N, M <= 50) + The location of fuel tank (start position) (0-based index) + The limit of the pump P (1 <= P <= 20) - Detail of the map will be given at next N rows, the value C of each cell represent the pipes (total 7 kind of pipes, 0 <= C <= 7), value 0 mean there is no pipe at that location. 5 => Total 5 test cases 5 6 2 1 3 => The size of the map is 5 x 6, starting point is (2,1), the limit of pump is 3 0 0 5 3 6 0 => The first row of the map 0 0 2 0 2 0 => The second row of the map 3 3 1 3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 5 6 2 2 6 3 0 0 0 0 3 2 0 0 0 0 6 1 3 1 1 3 1 2 0 2 0 0 2 0 0 4 3 1 1 10 10 4 3 9 0 0 0 0 0 0 0 0 0 0 0 0 0 7 5 0 5 0 0 0 0 0 3 2 2 6 0 0 0 0 0 4 7 2 2 2 7 0 0 4 0 3 0 1 1 2 2 0 0 5 0 5 6 1 1 1 1 6 2 5 7 4 1 2 0 0 4 6 0 0 5 3 1 7 0 2 2 6 5 7 7 3 2 1 1 7 1 0 2 7 3 4 0 0 4 0 5 1 0 1 ... [Output] - The total number of pipes that fuel can flow to Case #1 5 Case #2 15 Case #3 29 Code: #include <iostream> using namespace std; int qx[1000], qy[1000], f=-1,r=-1; void Push(int x, int y) { r++; qx[r]=x; qy[r]=y; } void Pop(int& x, int& y) { f++; x=qx[f]; y=qy[f]; } void Reset() { f=r=-1; } bool isEmpty() { return f==r; } int pumpLimit; int N, M; int pipes[50][50]; int visited[50][50]; int dtx[8][5]= { 0, 0,0,0,0, 0,-1,0,1,0, 0,-1,0,1,0, 0, 0,0,0,0, 0,-1,0,0,0, 0, 0,0,1,0, 0, 0,0,1,0, 0,-1,0,0,0, }; int dty[8][5]= { 0,0,0,0, 0, 0,0,1,0,-1, 0,0,0,0, 0, 0,0,1,0,-1, 0,0,1,0, 0, 0,0,1,0, 0, 0,0,0,0,-1, 0,0,0,0,-1, }; struct Point { int x, y; }; bool isValidConnection(int cd, int nd) { switch (cd) { case 1: return (nd==3); case 2: return (nd==4); case 3: return (nd==1); case 4: return (nd==2); } return false; } bool isValid(int x, int y, int N, int M) { return x >= 0 && x < N && y >= 0 && y < M; } int calculatePipes(Point start) { Reset(); Push(start.x, start.y); visited[start.x][start.y] = 1; int count = 0; int res=1; while (!isEmpty()) { int currentX,currentY; Pop(currentX,currentY); if (visited[currentX][currentY] == pumpLimit) break; for (int i = 1; i <= 4; i++) { if(dtx[pipes[currentX][currentY]][i]!=0 || dty[pipes[currentX][currentY]][i] != 0) { int nx = currentX + dtx[pipes[currentX][currentY]][i]; int ny = currentY + dty[pipes[currentX][currentY]][i]; if (isValid(nx, ny, N, M) && visited[nx][ny]==0 && pipes[nx][ny] != 0) { for(int j=1; j<=4; j++) { if(dtx[pipes[nx][ny]][j]!=0 || dty[pipes[nx][ny]][j] != 0) { if (isValidConnection(i,j)) { res++; Push(nx,ny); visited[nx][ny] = visited[currentX][currentY]+1; } } } } } } } return res; } int main() { //freopen("Text.txt","r",stdin); int T; cin >> T; for (int t = 1; t <= T; t++) { int startX, startY; cin >> N >> M >> startX >> startY >> pumpLimit; Point p; p.x=startX; p.y=startY; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> pipes[i][j]; visited[i][j]=0; } } int totalPipes = calculatePipes(p); cout << "Case #" << t <<endl<< totalPipes << endl; } return 0; }