当前位置:网站首页>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;
}
边栏推荐
- Stable Huawei micro certification, stable Huawei cloud database service practice
- 软考 系统架构设计师 简明教程 | 总目录
- Yyds dry goods inventory web components series (VII) -- life cycle of custom components
- 【leetcode】1189. Maximum number of "balloons"
- Several important classes in unity
- 颠覆你的认知?get和post请求的本质
- pd. to_ numeric
- MLAPI系列 - 04 - 网络变量和网络序列化【网络同步】
- Query the number and size of records in each table in MySQL database
- Practical development of member management applet 06 introduction to life cycle function and user-defined method
猜你喜欢
When debugging after pycharm remote server is connected, trying to add breakpoint to file that does not exist: /data appears_ sda/d:/segmentation
【leetcode】1189. Maximum number of "balloons"
Mlapi series - 04 - network variables and network serialization [network synchronization]
10个 Istio 流量管理 最常用的例子,你知道几个?
10 exemples les plus courants de gestion du trafic istio, que savez - vous?
Redis (replicate dictionary server) cache
Security xxE vulnerability recurrence (XXe Lab)
食品行业仓储条码管理系统解决方案
[disassembly] a visual air fryer. By the way, analyze the internal circuit
Record the pit of NETCORE's memory surge
随机推荐
E. Best Pair
Crawler notes: improve data collection efficiency! Use of proxy pool and thread pool
颠覆你的认知?get和post请求的本质
《2022年中国银行业RPA供应商实力矩阵分析》研究报告正式启动
10個 Istio 流量管理 最常用的例子,你知道幾個?
关于进程、线程、协程、同步、异步、阻塞、非阻塞、并发、并行、串行的理解
2328. 网格图中递增路径的数目(记忆化搜索)
脚本生命周期
AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
P2022 有趣的数(二分&数位dp)
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
2/10 parallel search set +bfs+dfs+ shortest path +spfa queue optimization
MySQL transaction isolation level
Recommendation system (IX) PNN model (product based neural networks)
Brief tutorial for soft exam system architecture designer | general catalog
ESP32(基于Arduino)连接EMQX的Mqtt服务器上传信息与命令控制
Practical development of member management applet 06 introduction to life cycle function and user-defined method
Database, relational database and NoSQL non relational database
User datagram protocol UDP
Viewing and verifying backup sets using dmrman