P2102 floor tile laying (DFS & greed)

P2102 Floor tile laying (dfs& greedy )

Enumerate each point as the upper left corner of the square to expand , Just judge the left boundary and the upper boundary , Then fill the square . Because the minimum requirement , So every time, we will judge whether the point in the upper right corner can be smaller , If not, just break, Otherwise, continue to expand .

Reference code

#include<bits/stdc++.h>
using namespace std;
char a[502][502];
int n,m,x,y;
bool same(char k,int x,int y)  // Judge (x,y) Can I put k
{
    
	if (x>n||y>m) return false;  // Judge whether it has crossed the boundary 
	if (a[x-1][y]==k&&a[x-1][y]) return false;
	if (a[x+1][y]==k&&a[x+1][y]) return false;
	if (a[x][y-1]==k&&a[x][y-1]) return false;
	if (a[x][y+1]==k&&a[x][y+1]) return false;  // Judge whether it is the same as that around 
	return true;
}
int pd(char k,int x1,int y1)  //x1,y1 Represents the coordinates of the upper left corner of the extended square 
{
    
	x=x1;
	y=y1;  //x,y Indicates row and column labels that cannot be extended 
	int flag=0;  //flag Indicates whether the extension is successful 
	for (int i=1;i<=n;i++)
	    if (!a[x][y1]&&!a[x1][y]&&same(k,x,y1)&&same(k,x1,y))  
          // Judge whether the current position has been let go and whether it is the same as the surrounding 
	    {
    
	    	char min1=0;
	    	for (char ch='A';ch<k;ch++)  // Judge whether the right position is smaller 
	    	    if (same(ch,x1,y)) 
	    	    {
    
	    	    	min1=ch;
	    	    	break;
				}
			if (min1) break;  // If you find a smaller one on the right , Just exit the extension 
	    	flag=1;
            x++;y++;  // Expand down 
		}
		else break;
	for (int i=x1;i<x;i++)  // because x,y Indicates that cannot be extended , So take the less than sign 
	    for (int j=y1;j<y;j++) a[i][j]=k;  // assignment , Expand 
	return flag;
}
int main()
{
    
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	    for (int j=1;j<=m;j++)
	        if (!a[i][j])
	            for (char k='A';k<='Z';k++)  // Enumerate the minimum values that can be placed in the current position from small to large  
	            {
    
	            	int x=pd(k,i,j);
	            	if (x) break;  // If you successfully put , It indicates that the current position has been put into the optimal value , sign out 
				}
	for (int i=1;i<=n;i++)
	{
    
		for (int j=1;j<=m;j++)
		    printf("%c",a[i][j]);
		printf("\n");
	} // Happy output 
	return 0;
}