shiwa_de_solution

 avatar
SSkyFire
java
2 months ago
3.6 kB
1
Indexable
Never
Công ty Shinwa muốn cải tạo lại các tòa nhà và tô màu chúng. 
Hãy để khuôn viên văn phòng có thể được ký hiệu là lưới n * m trong đó mỗi ô biểu thị một tòa nhà văn phòng. 
Chúng tôi sử dụng các ký tự Latinh viết hoa khác nhau để thể hiện các màu sắc khác nhau. 
Tuy nhiên, người quản lý phụ trách tô màu các tòa nhà là một người rất thú vị. 
Anh ta muốn loại bỏ các chu kỳ được tạo ra bởi các tòa nhà cùng màu. 
Chính thức chúng ta gọi một chuỗi các tòa nhà b1, b2, .... , b_k một chu kỳ nếu và chỉ khi t đáp ứng điều kiện sau:
1. Các tòa nhà k này khác nhau: nếu i ≠ j thì bi khác với bj.  
2. K ít nhất là 4.  
3. Tất cả các tòa nhà thuộc cùng một màu. 
4. Đối với tất cả 1 ≤ i ≤ k-1: bi và bi + 1 liền kề. 
Ngoài ra, bk và b1 cũng nên liền kề. 
Các tòa nhà x và y được gọi là liền kề nếu chúng có chung một cạnh.   
Xác định xem có tồn tại một chu kỳ trong khuôn viên văn phòng Shinwa hay không.   
Đầu vào 
Dòng đầu tiên chứa số lượng test case, t. 
Đối với mỗi trường hợp kiểm thử, dòng đầu tiên chứa hai số nguyên n và m (2≤n, m≤50): số hàng và cột của bảng. 
Sau đó n dòng theo sau, mỗi dòng chứa một chuỗi gồm m ký tự, thể hiện màu sắc của các tòa nhà trong mỗi dòng. 
Mỗi ký tự là một chữ cái Latinh viết hoa.  
Đầu ra đầu ra "Có" nếu tồn tại một chu kỳ trong khuôn viên trường và "Không" khác.

Sample Input:
3
3 4
AAAA
ABCA
AAAA
3 4
AAAA
ABCA
AADA
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB

Output:
Case 1: Yes
Case 2: No
Case 3: Yes

#include <iostream>
using namespace std;
int N,M;
char map[100][100];

int visited[100][100];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int start_x,start_y;
int flag=0;
void nhapmap()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin>> map[i][j];
			
		}
	}
}

void resetVisited()
{
	for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= M; j++)
			{
				visited[i][j]=0;
			
			}
		}
}

int inBound(int x, int y)
{
	if (1<=x && x<=N && 1<=y && y<=M)
	{
		return 1;
	}
	return 0;
}


void dfs(int x,int y, int count   )
{   
	
	for (int k = 0; k < 4; k++)
	{
		int new_x= x+dx[k];
		int new_y= y+dy[k];
		
		if ( inBound(new_x,new_y)  && map[new_x][new_y]==map[x][y]    )
		{
			
			if (visited[new_x][new_y]==0)
			{
			visited[new_x][new_y]=1+visited[x][y];
			
			dfs(new_x,new_y,count+1);
			
			
			}
			else if (visited[new_x][new_y]!=0 
			&& visited[new_x][new_y]+1< visited[x][y]
			&&count >=4 )
			{
				flag =1;
				
			}
			
		}
	}


}




int main()
{
//	  freopen("input.txt", "r", stdin);

	int T; cin >> T;
	
	for (int tc = 1; tc <= T; ++tc)
	{   
		cin>>N>>M;
		nhapmap();
		resetVisited();
		
	
		 flag=0;
		int level=1000;
		
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= M; j++)
			{
				if (visited[i][j]==0)
				{      
					   visited[i][j]=level;
					   dfs(i,j,1);
					
						if(flag==1)
						break;
					
					level--;

				}
				
			}
			if (flag ==1)
			{
				break;
			}

		}

		if (flag ==1)
		{
			cout <<"Case "<<tc<<":"<<" YES"<<endl;
		}else
			cout <<"Case "<<tc<<":"<<" NO"<<endl;

	}

	return 0;
}

Leave a Comment