Endoscope

https://www.hackerrank.com/contests/target-samsung-13-nov19/challenges/endoscope
 avatar
user_5448996
c_cpp
7 months ago
3.1 kB
2
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;

#define Max_N 55

int N, M, P;
int map[Max_N][Max_N];
int vis[Max_N][Max_N];

int dx[4] = { -1,0,1,0 };//tren _ phai _ duoi _ trai
int dy[4] = { 0,1,0,-1 };
int ans;

//const int pipe[8][4] = { {0,0,0,0}, {1,1,1,1},{1,0,1,0},{0,1,0,1},{1,1,0,0},{0,1,1,0},{0,0,1,1},{1,0,0,1} };

struct Pipe{
	int up, right, left, down;
}pipe[8];

void init()
{
	pipe[0].up = 0;
	pipe[0].right = 0;
	pipe[0].down = 0;
	pipe[0].left = 0;

	pipe[1].up = 1;
	pipe[1].right = 1;
	pipe[1].down = 1;
	pipe[1].left = 1;

	pipe[2].up = 1;
	pipe[2].right = 0;
	pipe[2].down = 1;
	pipe[2].left = 0;

	pipe[3].up = 0;
	pipe[3].right = 1;
	pipe[3].down = 0;
	pipe[3].left = 1;

	pipe[4].up = 1;
	pipe[4].right = 1;
	pipe[4].down = 0;
	pipe[4].left = 0;

	pipe[5].up = 0;
	pipe[5].right = 1;
	pipe[5].down = 1;
	pipe[5].left = 0;
	
	pipe[6].up = 0;
	pipe[6].right = 0;
	pipe[6].down = 1;
	pipe[6].left = 1;

	pipe[7].up = 1;
	pipe[7].right = 0;
	pipe[7].down = 0;
	pipe[7].left = 1;
}

struct Node 
{
	int x, y;
}Queue[Max_N*Max_N],Hugo;

int front, rear;
void Qinit()
{
	front = rear = -1;
}
bool isEmpty()
{
	return front == rear;
}

void enQueue(int r, int c)
{
	rear++;
	Queue[rear].x = r;
	Queue[rear].y = c;
}

Node deQueue()
{
	return Queue[++front];
}

bool insize(int r, int c)
{
	return (r >= 0 && c >= 0 && r < N && c < M);
}

void bfs()
{
	Qinit();
	enQueue(Hugo.x, Hugo.y);
	vis[Hugo.x][Hugo.y] = 1;
	while (!isEmpty())
	{
		Node now = deQueue();
		if (vis[now.x][now.y] == P)
			break;
		for (int i = 0; i < 4; i++)
		{
			int nr = now.x + dx[i];
			int nc = now.y + dy[i];
			if (!insize(nr, nc)) continue;
			if (i==0 && vis[nr][nc] == 0 && map[nr][nc]!=0)// tren
			{
				if (pipe[map[now.x][now.y]].up == 1 && pipe[map[nr][nc]].down == 1)
				{
					enQueue(nr, nc);
					vis[nr][nc] = vis[now.x][now.y] + 1;
					ans++;
				}
			}
			if (i == 1 && vis[nr][nc] == 0 && map[nr][nc] != 0)// phai
			{
				if (pipe[map[now.x][now.y]].right == 1 && pipe[map[nr][nc]].left == 1)
				{
					enQueue(nr, nc);
					vis[nr][nc] = vis[now.x][now.y] + 1;
					ans++;
				}
			}
			if (i == 2 && vis[nr][nc] == 0 && map[nr][nc] != 0)//duoi
			{
				if (pipe[map[now.x][now.y]].down == 1 && pipe[map[nr][nc]].up == 1)
				{
					enQueue(nr, nc);
					vis[nr][nc] = vis[now.x][now.y] + 1;
					ans++;
				}
			}
			if (i == 3 && vis[nr][nc] == 0 && map[nr][nc] != 0)//trai
			{
				if (pipe[map[now.x][now.y]].left == 1 && pipe[map[nr][nc]].right == 1)
				{
					enQueue(nr, nc);
					vis[nr][nc] = vis[now.x][now.y] + 1;
					ans++;
				}
			}
		}
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	init();
	for (int tc = 1; tc <= T; tc++) 
	{
		cin >> N >> M;
		cin >> Hugo.x >> Hugo.y;
		cin >> P;
		for (int i = 0; i < N; i++)
		{
			for (int  j = 0; j < M; j++)
			{
				cin >> map[i][j];
				vis[i][j] = 0;
			}
		}
		ans = 1;
		bfs();
		cout << ans << endl;
	}
	return 0;
}