Untitled

 avatar
unknown
plain_text
a year ago
6.4 kB
6
Indexable
#include<iostream>
using namespace std;


int t, m, n, a[51][51], p, r, c, cnt, ploang;
int front , rear,q1[51 * 51] , q2[51 * 51], visited[51][51];

int dx[] = {-1,0,1,0};
int dy[] = {0, 1,0,-1};

//struct Queue
//{
//	void initQueue()
//	{
//		front = rear = -1;
//	}
//	
//	int isEmpty()
//	{
//		if(front == rear)
//			return 1;
//
//		return 0;
//	}
//
//	void enQueue(int x)
//	{
//		rear++;
//		q[rear] = x;
//	}
//
//	int deQueue()
//	{
//		if(!isEmpty())
//		{
//			front++;
//			return q[front];
//		}
//		return -1;
//	}
//	
//
//
//};

//int noi_ong(int x, int y , int r, int c)
//{
//	if(a[x][y] == 1)
//	{
//		if(a[r][c] == 1)
//		{
//			if(r == x -1 && c == y || r == x && c == y + 1 || r == x + 1 && c == y || r == x && c == y -1)
//				return 1;
//		}
//		else if(a[r][c] == 2)
//		{
//			if(r == x + 1 && c == y || r == x - 1 && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 3)
//		{
//			if(r == x && c == y + 1 || r == x && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 4)
//		{
//			if(r == x && c == y - 1 || r == x + 1 && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 5)
//		{
//			if(r == x -1 && c == y || r == x && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 6)
//		{
//			if(r == x - 1 && c == y || r == x && c == y + 1)
//				return 1;
//		}
//		else if(a[r][c] == 7)
//		{
//			if(r == x + 1 && c == y || r == x && c == y + 1)
//				return 1;
//		}
//	}
//	else if(a[x][y] == 2)
//	{
//		if(a[r][c] == 1)
//		{
//			if(r == x - 1 && c == y || r == x + 1 && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 2)
//		{
//			if(r == x - 1 && c == y || r == x + 1 && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 4)
//		{
//			if(r == x + 1 && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 5)
//		{
//			if(r == x - 1 && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 6)
//		{
//			if(r == x - 1 && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 7)
//		{
//			if(r == x + 1 && c == y)
//				return 1;
//		}
//	}
//	else if(a[x][y] == 3)
//	{
//		if(a[r][c] == 1)
//		{
//			if(r == x && c == y + 1 || r == x && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 3)
//		{
//			if(r == x && c == y + 1 || r == x && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 4)
//		{
//			if(r == x  && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 5)
//		{
//			if(r == x  && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 6)
//		{
//			if(r == x  && c == y + 1)
//				return 1;
//		}
//		else if(a[r][c] == 7)
//		{
//			if(r == x  && c == y + 1)
//				return 1;
//		}
//	}
//	else if(a[x][y] == 4)
//	{
//		if(a[r][c] == 1)
//		{
//			if(r == x -1 && c == y || r == x && c == y + 1)
//				return 1;
//		}
//		else if(a[r][c] == 2)
//		{
//			if(r == x -1  && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 3)
//		{
//			if(r == x  && c == y + 1)
//				return 1;
//		}
//		else if(a[r][c] == 5)
//		{
//			if(r == x -1  && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 6)
//		{
//			if(r == x -1 && c == y || r == x && c == y + 1)
//				return 1;
//		}
//		else if(a[r][c] == 7)
//		{
//			if(r == x  && c == y + 1)
//				return 1;
//		}
//	}
//	else if(a[x][y] == 5)
//	{
//			if(a[r][c] == 1)
//		{
//			if(r == x + 1 && c == y || r == x && c == y + 1)
//				return 1;
//		}
//		else if(a[r][c] == 2)
//		{
//			if(r == x + 1  && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 3)
//		{
//			if(r == x  && c == y + 1)
//				return 1;
//		}
//		else if(a[r][c] == 4)
//		{
//			if(r == x + 1  && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 7)
//		{
//			if(r == x + 1 && c == y || r == x && c == y + 1)
//				return 1;
//		}
//		else if(a[r][c] == 6)
//		{
//			if(r == x  && c == y + 1)
//				return 1;
//		}
//	}
//	else if(a[x][y] == 6)
//	{
//		if(a[r][c] == 1)
//		{
//			if(r == x + 1 && c == y || r == x && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 2)
//		{
//			if(r == x + 1  && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 3)
//		{
//			if(r == x  && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 4)
//		{
//			if(r == x  && c == y - 1 || r == x + 1  && c == y )
//				return 1;
//		}
//		else if(a[r][c] == 5)
//		{
//			if(r == x && c == y -1)
//				return 1;
//		}
//		else if(a[r][c] == 7)
//		{
//			if(r == x + 1  && c == y)
//				return 1;
//		}
//	}
//	else if(a[x][y] == 7)
//	{
//		if(a[r][c] == 1)
//		{
//			if(r == x - 1 && c == y || r == x && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 2)
//		{
//			if(r == x - 1  && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 3)
//		{
//			if(r == x  && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 4)
//		{
//			if(r == x  && c == y - 1)
//				return 1;
//		}
//		else if(a[r][c] == 5)
//		{
//			if(r == x && c == y -1 || r == x - 1  && c == y)
//				return 1;
//		}
//		else if(a[r][c] == 6)
//		{
//			if(r == x - 1  && c == y)
//				return 1;
//		}
//	}
//	return 0;
//}

bool ket_noi[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}
};



void BFS(int x, int y)
{
	q1[++rear] = x;
	q2[rear] = y;

	while (front != rear)
	{
		int u = q1[++front];
		int v = q2[front];

		if(visited[u][v] == p)
			break;

		for (int k = 0; k < 4; k++)
		{
			if(!ket_noi[a[u][v]][k])
				continue;

			int tx = u + dx[k];
			int ty = v + dy[k];

			if( tx < 0 || tx == n || ty < 0 || ty == m || !a[tx][ty])
				continue;
			
	//		int check = noi_ong(u, v, tx , ty);
			
			if(!visited[tx][ty] && ket_noi[a[tx][ty]][(k + 2) % 4] ) 
			{
				visited[tx][ty] = visited[u][v] + 1;
				q1[++rear] = tx;
				q2[rear] = ty;
				cnt++;
			}
		}
		
	}


}


int main()
{
	//freopen("t.txt", "r", stdin);
	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		cin >> m >> n >> r >> c >> p;

			for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
			visited[i][j] = 0;
		}
	}

	cnt = 1;
	visited[r][c] = 1;
	front = -1;
	rear = -1 ;

	BFS(r, c);
	cout <<"Case #" << tc << endl<< cnt << endl;


	}

	return 0;

}
Editor is loading...
Leave a Comment