Untitled

- 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

//
Trường hợp #1

5

Trường hợp #2

15

Trường hợp #3

29

/////
#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;
}