洛谷p3956 棋盘（NOIP2017 t3）
2024-09-05 21:04:35
在noip考场上本来以为只能骗暴力分，没想到最后A了；
本蒟蒻的做法比较简（zhi）单（zhang）：记忆化深搜（考场上本来是想打广搜的，但我深搜稳一点就这样打了）；
具体：每个点用一个f数组记录当前位置到这个点的最优值，如果大于等于就跳出，否则更新继续做；
深搜的过程中开个桶记录每个点是否无色，如果无色要注意下个走的点不能有色，如果下个点要走无色的格子，这里可以采取一个贪心的策略：把那个格子的颜色设置成当前这个格子的颜色；
要注意的是：走的过程中是可以向四个方向走的，并且要回溯（我一个dalao同学就忘了回溯才拿了40）；
附蒟蒻丑陋的代码。。。
var n,m,i,j,k,l,x,y,z:longint;
a:array[..,..] of longint;
b:array[..,..] of boolean;
f:array[..,..] of longint;
procedure try(x,y,z,kk:longint);
begin
if (x>m)or(y>m)or(x<)or(y<) then exit;
if b[x,y] then exit;
if z>=f[x,y] then exit;
if (x=m)and(y=m) then
begin
if z<k then k:=z;
exit;
end;
f[x,y]:=z;
inc(l);
b[x,y]:=true;
if a[x,y]= then
begin
if a[x+,y]= then try(x+,y,z,) else
if a[x+,y]= then try(x+,y,z+,) else
if kk= then
begin
a[x+,y]:=;
try(x+,y,z+,);
a[x+,y]:=;
end;
if a[x,y+]= then try(x,y+,z,) else
if a[x,y+]= then try(x,y+,z+,) else
if kk= then
begin
a[x,y+]:=;
try(x,y+,z+,);
a[x,y+]:=;
end;
if a[x-,y]= then try(x-,y,z,) else
if a[x-,y]= then try(x-,y,z+,) else
if kk= then
begin
a[x-,y]:=;
try(x-,y,z+,);
a[x-,y]:=;
end;
if a[x,y-]= then try(x,y-,z,) else
if a[x,y-]= then try(x,y-,z+,) else
if kk= then
begin
a[x,y-]:=;
try(x,y-,z+,);
a[x,y-]:=;
end;
end else
if a[x,y]= then
begin
if a[x+,y]= then try(x+,y,z+,) else
if a[x+,y]= then try(x+,y,z,) else
if kk= then
begin
a[x+,y]:=;
try(x+,y,z+,);
a[x+,y]:=;
end;
if a[x,y+]= then try(x,y+,z+,) else
if a[x,y+]= then try(x,y+,z,) else
if kk= then
begin
a[x,y+]:=;
try(x,y+,z+,);
a[x,y+]:=;
end;
if a[x-,y]= then try(x-,y,z+,) else
if a[x-,y]= then try(x-,y,z,) else
if kk= then
begin
a[x-,y]:=;
try(x-,y,z+,);
a[x-,y]:=;
end;
if a[x,y-]= then try(x,y-,z+,) else
if a[x,y-]= then try(x,y-,z,) else
if kk= then
begin
a[x,y-]:=;
try(x,y-,z+,);
a[x,y-]:=;
end;
end;
b[x,y]:=false;
end;
begin
assign(input,'chess.in');
assign(output,'chess.out');
reset(input);
rewrite(output);
k:=maxlongint div ;
read(m,n);
for i:= to m do
for j:= to m do f[i,j]:=maxlongint;
for i:= to n do
begin
read(x,y,z);
a[x,y]:=z+;
end;
try(,,,);
if k=maxlongint div then write(-) else
write(k);
close(input);
close(output);
end.
最新文章
- Winform端上传图片到服务器
- OpenSSL - 文件和字符MD5加密实现
- 我的IT相关网址收藏
- 为什么大型网站前端使用PHP后台逻辑用Java
- AWR
- 比nerdtree更好的文件浏览器：vimfiler
- Mysql中查看表的类型InnoDB
- 数据库 版本号是 661，打不开。此server支持 655 和更早的版本号。不支持降级路径
- js浏览器兼容
- org.apache.hadoop.security.AccessControlException: Permission denied: user=?, access=WRITE, inode="/":hadoop:supergroup:drwxr-xr-x 异常解决
- TSQL：判定一段数组连续的数字段有多少的方案
- 使用Linq查找重复
- springboot 静态注入 单例
- 1-STM32嵌入LUA开发(控制小灯闪耀)
- saltStack运维工具的部署及master迁移实现的过程详解
- OpenCV支持向量机(SVM)介绍
- 非接触IC卡中typeA卡和typeB卡的区别--总结，二者的调制方式和编码方式不同
- js判断软键盘是否开启弹出
- Node.js-Usage & Example
- Merge join、Hash join、Nested loop join对比分析