Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.3 kB
6
Indexable
Never
pipe network

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