ZOJ 1002 Fire Net(dfs)
2024-09-06 01:23:01
嗯...
题目链接:https://zoj.pintia.cn/problem-sets/91827364500/problems/91827364501
这道题是想出来则是一道很简单的dfs:
将一个4*4的地图给每一个点排序,如下图:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
设一个点为第k个点,那么它的坐标为(k/n,k%n),根据这个进行dfs,当k == n * n是退出dfs。如果k < n *n,就继续dfs,判断是否能放下,即要放的这个点为空地并且横、纵上都没有东西,最后注意回溯。
#include<cstdio>
#include<iostream>
#include<cstring> using namespace std; int n, ans;
char g[][]; inline bool canput(int x, int y){
for(int i = x - ; i >= && g[i][y] != 'X'; i--){
if(g[i][y] == 'O') return ;
}
for(int i = y - ; i >= && g[x][i] != 'X'; i--){
if(g[x][i] == 'O') return ;
}
return ;
} inline void dfs(int k, int cnt){
int x, y;
if(k == n * n){
if(cnt > ans) ans = cnt;
return;
}
else{
x = k / n;
y = k % n;
if(g[x][y] == '.' && canput(x, y)){
g[x][y] = 'O';
dfs(k + , cnt + );
g[x][y] = '.';
}
dfs(k + , cnt);
}
} int main(){
while(~scanf("%d", &n) && n){
ans = ;
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
cin >> g[i][j];
}
}
dfs(, );
printf("%d\n", ans);
}
return ;
}
AC代码
最新文章
- ASP.NET Web API 控制器创建过程(一)
- 一个批量移除BOM头的bash脚本
- js实现无刷新表单提交文件,将ajax请求转换为form请求方法
- windows phone listbox虚拟化(下)
- Swift - 09 - Optionals
- Hibernate之总结
- Android基调(十六)- Service:startService()、stopService()、bindService()、unbindService()加
- 从零開始开发Android版2048 (四) 分数、重置、结束
- 【工具】JAVA 在单元读取文件并比较
- NOIP2010-普及组复赛-第二题-接水问题
- 2017-3-2 C#基础 结构体
- iOS开发中UIPopoverController的使用详解
- centos 7安装vnc服务端&;vnc客户端连接
- Encrypt2
- Mysql的时间类型问题
- WebSocket原理与实践
- Linux 局域网同步时间
- Python中特殊函数和表达式lambda,filter,map,reduce
- 【Java知识点专项练习】之 volatile 关键字的功能
- Centos重新启动网络配置文件,/etc/resolv.conf被覆盖或清空问题解决
热门文章
- FPM 0.08不能运行破解办法……
- (转)漫游Kafka入门篇之简单介绍
- No serializer found for class org.hibernate.proxy.pojo.bytebuddy.ByteBuddyInterceptor
- 使用BeautifulSoup爬取汽车之家新闻
- IntelliJ IDEA 2017.3尚硅谷-----版本控制(Version Control)
- Virtual Judge POJ 1328	Radar Installation
- flutter_html 和 WebView 解析html 和 build.gradle源码
- $ ssh -T -v git@github.com_在本地用ssh连接github出错_git@github.com: Permission denied (publickey).
- 【游戏体验】I Paid For It!(火柴人破坏狂)
- winform学习(6)控件的对齐、比例、定位操作