Untitled
unknown
plain_text
2 years ago
6.4 kB
4
Indexable
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>
#define max 1000000
using namespace std;
int n,m;
int queue[2][1000];
int front =-1 ;
int rear=-1;
int map[60][60];
int visit[180][180];
int Si, Sj;
int limit;
int di[4]={0, 0, 1, -1};
int dj[4]={1,-1, 0, 0};
int ans;
int phai[8][8] = { 0, 0, 0, 0, 0, 0, 0, 0, // lap x2 sang phai cua x1
0, 1, 0, 1, 0, 0, 1 ,1,
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 1, 0, 0, 1, 1,
0, 1, 0, 1, 0, 0, 1, 1,
0, 1, 0, 1, 0, 0, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0};
int trai[8][8] = { 0, 0, 0, 0, 0, 0, 0, 0, // lap x2 sang trai x1
0, 1, 0, 1, 1, 1, 0 ,0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 1, 1, 1, 0 ,0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 1, 1, 1, 0, 0,
0, 1, 0, 1, 1, 1, 0, 0};
int tren[8][8] = { 0, 0, 0, 0, 0, 0, 0, 0, // lap x2 len tren x1
0, 1, 1, 0, 0, 1, 1 ,0,
0, 1, 1, 0, 0, 1, 1 ,0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 0, 0, 1, 1 ,0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 0, 0, 1, 1 ,0};
int duoi[8][8] = { 0, 0, 0, 0, 0, 0, 0, 0, // lap x2 o duoi x1
0, 1, 1, 0, 1, 0, 0 ,1,
0, 1, 1, 0, 1, 0, 0 ,1,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 0, 1, 0, 0 ,1,
0, 1, 1, 0, 1, 0, 0 ,1,
0, 0, 0, 0, 0, 0, 0, 0};
void push(int i, int j){
if(rear == max-1) rear =-1;
rear++;
queue[0][rear]=i;
queue[1][rear]=j;
}
void pop(){
if(front == max-1) front =-1;
front++;
}
bool IsEmpty(){
return front == rear;
}
bool checkIn(int i, int j){
if(i>=0 && i < n && j >=0 && j < m) return true;
return false;
}
void Reset() {
front=rear=-1;
for(int i=0; i <180 ; i++){
for(int j=0; j<180; j++){
visit[i][j] =0;
}
}
}
void bfs( int i ,int j){
Reset();
push(i,j);
visit[i][j] =1;
while(!IsEmpty()){
pop();
int i1=queue[0][front];
int j1=queue[1][front];
for(int a=0; a<4; a++){
int i2 = i1 + di[a];
int j2 = j1 + dj[a];
if(a==0 && checkIn(i2, j2) && visit[i2][j2] ==0 && map[i2][j2] !=0 && phai[map[i1][j1]][map[i2][j2]] == 1){
visit[i2][j2] =visit[i1][j1] +1;
push(i2, j2);
}
if(a==1 && checkIn(i2, j2) && visit[i2][j2] ==0 && map[i2][j2] !=0 && trai[map[i1][j1]][map[i2][j2]] == 1){
visit[i2][j2] =visit[i1][j1] +1;
push(i2, j2);
}
if(a==2 && checkIn(i2, j2) && visit[i2][j2] ==0 && map[i2][j2] !=0 && duoi[map[i1][j1]][map[i2][j2]] == 1){
visit[i2][j2] =visit[i1][j1] +1;
push(i2, j2);
}
if(a==3 && checkIn(i2, j2) && visit[i2][j2] ==0 && map[i2][j2] !=0 && tren[map[i1][j1]][map[i2][j2]] == 1){
visit[i2][j2] =visit[i1][j1] +1;
push(i2, j2);
}
}
}
}
void dem(){
for(int i=0; i <180 ; i++){
for(int j=0; j<180; j++){
if(visit[i][j] !=0 && visit[i][j] <= limit) ans++;
}
}
}
int main(){
//freopen("Text.txt" ,"r", stdin);
int test;
cin >> test;
for(int tc=1; tc <= test; tc++){
cin >> n >> m >> Si >> Sj >> limit;
for(int i=0; i <n ; i++){
for(int j=0; j<m; j++){
cin >> map[i][j];
}
}
bfs(Si,Sj);
ans = 0;
dem();
cout << "Case #" << tc << endl;
cout << ans << endl;
}
return 0;
}
Editor is loading...