Untitled
unknown
plain_text
2 years ago
7.3 kB
6
Indexable
Mạng lưới đường ống
Mạng lưới đường ống
Công ty chúng tôi đã thiết lập một mạng lưới đường ống để phân phối nhiên liệu trong nhà máy. Trong mạng lưới đó, một bình nhiên liệu sẽ được đặt tại một vị trí trong nhà máy. Từ đó, nhiên liệu sẽ được phân phối đến nơi khác bằng mạng lưới đường ống.
Có tổng cộng 7 loại ống, được đánh dấu từ 1-7 như hình dưới đây:
Chỉ các đường ống được kết nối mới có thể cho phép nhiên liệu đi qua chúng. Hai đường ống được kết nối nếu chúng có một điểm cuối chung. Chẳng hạn:
- Trong trường hợp này, nhiên liệu có thể chảy từ A đến B
- Nhưng trong trường hợp này, nhiên liệu không thể chảy từ A đến B (Ống trong A không có bất kỳ điểm cuối chung nào với đường ống trong B)
Tuy nhiên, máy bơm được sử dụng để phân phối nhiên liệu có giới hạn về hiệu suất của nó. Tùy thuộc vào loại của nó, máy bơm chỉ có thể bơm nhiên liệu đến giới hạn của nó. Ví dụ, giả sử giới hạn của bơm là 3, có nghĩa là từ vị trí xuất phát, nhiên liệu chỉ có thể chảy đến nơi mờ nhất cách đó 3 bước (bao gồm cả điểm xuất phát).
Đưa ra bản đồ mạng lưới đường ống, vị trí của bình nhiên liệu (vị trí bắt đầu), giới hạn của bơm, hãy viết một chương trình để tính tổng số đường ống mà nhiên liệu có thể chảy đến.
Ví dụ 1: Trong trường hợp này, chiều cao của bản đồ (N) là 5, chiều dài của bản đồ (M) là 6, vị trí của bình nhiên liệu là (2,1), giới hạn của bơm là 3
- Nhiên liệu đầu tiên được bơm đến vị trí (2,1)
- Thứ hai, nhiên liệu chảy đến vị trí (2,0) và (2,2)
- Thứ ba, nhiên liệu chảy đến vị trí (1,2) và (2,3)
Khi đạt đến giới hạn của bơm, nhiên liệu không thể chảy thêm nữa. Do đó, tổng số đường ống mà nhiên liệu có thể chảy đến là 5.
Ví dụ 2: Trong trường hợp này, chiều cao của bản đồ (N) là 5, chiều dài của bản đồ (M) là 6, vị trí của bình nhiên liệu là (2,2), giới hạn của bơm là 6. Câu trả lời là 15.
[Hạn chế]
- Bình nhiên liệu luôn được đặt ở vị trí có đường ống
[Đầu vào]
- Số test case T (T <= 50)
- Trong mỗi TC, hàng đầu tiên sẽ cho:
+ Kích thước bản đồ N x M (5 <= N, M <= 50)
+ Vị trí bình xăng (vị trí xuất phát) (chỉ số 0 điểm)
+ Giới hạn của bơm P (1 <= P <= 20)
- Chi tiết bản đồ sẽ được đưa ra ở các hàng N tiếp theo, giá trị C của mỗi ô đại diện cho các đường ống (tổng cộng 7 loại ống, 0 < = C < = 7), giá trị 0 có nghĩa là không có đường ống tại vị trí đó.
5 = > Tổng cộng 5 trường hợp kiểm thử
5 6 2 1 3 => Kích thước của bản đồ là 5 x 6, điểm xuất phát là (2,1), giới hạn của máy bơm là 3
0 0 5 3 6 0 => Hàng đầu tiên của bản đồ
0 0 2 0 2 0 => Hàng thứ hai của bản đồ
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 <> <>
...
[Đầu ra]
- Tổng số đường ống mà nhiên liệu có thể chảy đến
Trường hợp #1
5
Trường hợp #2
15
Trường hợp #3
29
///////////////////////////////////////////////////
#include<iostream>
#define max 10
#define oo 1000000
using namespace std;
int n, m, xb, yb, gh_b;
int Map[max][max], visit[max][max];
int front, rear;
int qx[oo], qy[oo];
int ans;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
/////// 4 huong
// co 8 truong hop:
// tinh ca truong hop khong co duong ong va 7 truong hop de bai cho
int tren[8][8]=
{
{0,0,0,0,0,0,0,0},
{0,1,2,0,0,5,6,0},
{0,1,2,0,0,5,6,0},
{0,0,0,0,0,0,0,0},
{0,1,2,0,0,5,6,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,1,2,0,0,5,6,0},
};
int duoi[8][8]=
{
{0,0,0,0,0,0,0,0},
{0,1,2,0,4,0,0,7},
{0,1,2,0,4,0,0,7},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,1,2,0,4,0,0,7},
{0,1,2,0,4,0,0,7},
{0,0,0,0,0,0,0,0}
};
int trai[8][8]=
{
{0,0,0,0,0,0,0,0},
{0,1,0,3,4,5,0,0},
{0,0,0,0,0,0,0,0},
{0,1,0,3,4,5,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,1,0,3,4,5,0,0},
{0,1,0,3,4,5,0,0}
};
int phai[8][8]=
{
{0,0,0,0,0,0,0,0},
{0,1,0,3,0,0,6,7},
{0,0,0,0,0,0,0,0},
{0,1,0,3,0,0,6,7},
{0,1,0,3,0,0,6,7},
{0,1,0,3,0,0,6,7},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0}
};
////////////////////
void push(int x, int y){
if(front == -1) front = 0;
rear++;
qx[rear] = x;
qy[rear] = y;
}
void pop(){
if(front >= rear) front = rear = -1;
else front++;
}
bool isEmpty(){
return front == -1;
}
bool check(int x, int y){
if(x >= 0 && x < n && y >= 0 && y < m) return true;
return false;
}
void reset(){
ans = 1;// auto dem duoc 1 vi tri tai cho do dau
front = rear = -1;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
visit[i][j] = 0;
}
}
}
void bfs(int x, int y){
visit[x][y] = 1;
push(x, y);
while(!isEmpty()){
int topx = qx[front];
int topy = qy[front];
pop();
if(visit[topx][topy] == gh_b) break;
for(int i = 0; i < 4; i++){
int tempx = topx + dx[i];
int tempy = topy + dy[i];
if(check(tempx,tempy) && visit[tempx][tempy] == 0 && Map[tempx][tempy] != 0){
// vi tri = tren duoi trai phai
if(i == 0){
if(tren[Map[topx][topy]][Map[tempx][tempy]] != 0){
visit[tempx][tempy] = visit[topx][topy]+1;
ans++;
push(tempx,tempy);
}
}
if(i == 1){
if(duoi[Map[topx][topy]][Map[tempx][tempy]] != 0){
visit[tempx][tempy] = visit[topx][topy]+1;
ans++;
push(tempx,tempy);
}
}
if(i == 2){
if(trai[Map[topx][topy]][Map[tempx][tempy]] != 0){
visit[tempx][tempy] = visit[topx][topy]+1;
ans++;
push(tempx,tempy);
}
}
if(i == 3){
if(phai[Map[topx][topy]][Map[tempx][tempy]] != 0){
visit[tempx][tempy] = visit[topx][topy] + 1;
ans++;
push(tempx,tempy);
}
}
}
}
}
}
int main(){
freopen("input.txt","r",stdin);
int tc;
cin >> tc;
for(int T = 1; T <= tc; T++){
cin >> n >> m >> xb >> yb >> gh_b;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> Map[i][j];
}
}
reset();
bfs(xb, yb);
//IN();
cout << "Case #" << T << endl;
cout << ans << endl;
}
return 0;
}Editor is loading...