当前位置:网站首页>P2102 floor tile laying (DFS & greed)
P2102 floor tile laying (DFS & greed)
2022-07-06 04:16:00 【Harris-H】
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;
}
边栏推荐
- AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
- lora网关以太网传输
- VPP performance test
- Slow SQL fetching and analysis of MySQL database
- Développement d'un module d'élimination des bavardages à clé basé sur la FPGA
- hashlimit速率控制
- During pycharm debugging, the view is read only and pause the process to use the command line appear on the console input
- pd. to_ numeric
- 【leetcode】22. bracket-generating
- POI add border
猜你喜欢
自动化测试的好处
IDEA编译JSP页面生成的class文件路径
Chinese brand hybrid technology: there is no best technical route, only better products
AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
Solution to the problem that the root account of MySQL database cannot be logged in remotely
Figure application details
[Zhao Yuqiang] deploy kubernetes cluster with binary package
Stack and queue
DM8 archive log file manual switching
Overturn your cognition? The nature of get and post requests
随机推荐
【leetcode】22. bracket-generating
Benefits of automated testing
Global and Chinese markets for medical gas manifolds 2022-2028: Research Report on technology, participants, trends, market size and share
User datagram protocol UDP
One question per day (Mathematics)
Tips for using dm8huge table
Unity中几个重要类
P2022 有趣的数(二分&数位dp)
How to execute an SQL statement in MySQL
DM8 backup set deletion
Practical development of member management applet 06 introduction to life cycle function and user-defined method
Class A, B, C networks and subnet masks in IPv4
10個 Istio 流量管理 最常用的例子,你知道幾個?
Thread sleep, thread sleep application scenarios
Codeforces Round #770 (Div. 2) B. Fortune Telling
Basic knowledge of binary tree, BFC, DFS
Use js to complete an LRU cache
hashlimit速率控制
/usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
80% of the diseases are caused by bad living habits. There are eight common bad habits, which are both physical and mental