当前位置:网站首页>P2102 地砖铺设(dfs&贪心)
P2102 地砖铺设(dfs&贪心)
2022-07-06 04:11:00 【Harris-H】
P2102 地砖铺设(dfs&贪心)
枚举每个点作为正方形左上角进行扩展,只需对左边界和上边界进行判断即可,然后正方形填充。因为要求最小,所以每次就特判右上角的点是否能更小,如果不行就break,否则就继续扩展。
参考代码
#include<bits/stdc++.h>
using namespace std;
char a[502][502];
int n,m,x,y;
bool same(char k,int x,int y) //判断(x,y)是否可以放入k
{
if (x>n||y>m) return false; //判断有没有越界
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; //判断有没有与四周相同的
return true;
}
int pd(char k,int x1,int y1) //x1,y1表示扩展正方形的左上角坐标
{
x=x1;
y=y1; //x,y表示无法扩展到的行标和列标
int flag=0; //flag表示扩展是否成功
for (int i=1;i<=n;i++)
if (!a[x][y1]&&!a[x1][y]&&same(k,x,y1)&&same(k,x1,y))
//判断当前位置有没有被放过并且有没有与周围相同
{
char min1=0;
for (char ch='A';ch<k;ch++) //判断右侧位置能否更小
if (same(ch,x1,y))
{
min1=ch;
break;
}
if (min1) break; //如果发现右侧可以放更小的,就退出扩展
flag=1;
x++;y++; //往下扩展
}
else break;
for (int i=x1;i<x;i++) //因为x,y表示无法扩展,所以取小于号
for (int j=y1;j<y;j++) a[i][j]=k; //赋值,扩展
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++) //从小到大枚举当前位置可以放的最小值
{
int x=pd(k,i,j);
if (x) break; //如果成功放入,说明当前位置已经放入了最优值,退出
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
printf("%c",a[i][j]);
printf("\n");
} //愉快输出
return 0;
}
边栏推荐
- In depth MySQL transactions, stored procedures and triggers
- Script lifecycle
- AcWing 243. A simple integer problem 2 (tree array interval modification interval query)
- Ipv4中的A 、B、C类网络及子网掩码
- 10 exemples les plus courants de gestion du trafic istio, que savez - vous?
- 软考 系统架构设计师 简明教程 | 总目录
- Record the pit of NETCORE's memory surge
- 【按鍵消抖】基於FPGA的按鍵消抖模塊開發
- VPP性能测试
- Ks003 mall system based on JSP and Servlet
猜你喜欢
Facebook等大廠超十億用戶數據遭泄露,早該關注DID了
Proof of Stirling formula
颠覆你的认知?get和post请求的本质
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
Record the pit of NETCORE's memory surge
图应用详解
WPF effect Article 191 box selection listbox
DM8 backup set deletion
Solution of storage bar code management system in food industry
【按键消抖】基于FPGA的按键消抖模块开发
随机推荐
关于进程、线程、协程、同步、异步、阻塞、非阻塞、并发、并行、串行的理解
Cross domain and jsonp details
DM8 archive log file manual switching
PTA tiantisai l1-078 teacher Ji's return (15 points) detailed explanation
1291_Xshell日志中增加时间戳的功能
Overturn your cognition? The nature of get and post requests
Comprehensive ability evaluation system
Global and Chinese markets for otolaryngology devices 2022-2028: Research Report on technology, participants, trends, market size and share
SSTI template injection explanation and real problem practice
User datagram protocol UDP
Stable Huawei micro certification, stable Huawei cloud database service practice
图应用详解
查询mysql数据库中各表记录数大小
Security xxE vulnerability recurrence (XXe Lab)
R note prophet
Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
MySQL learning record 13 database connection pool, pooling technology, DBCP, c3p0
题解:《单词覆盖还原》、《最长连号》、《小玉买文具》、《小玉家的电费》
Viewing and verifying backup sets using dmrman
Network security - Security Service Engineer - detailed summary of skill manual (it is recommended to learn and collect)