hdu1045 Fire Net (dfs)_hdu 1045-程序员宅基地

Fire Net

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11697 Accepted Submission(s): 7014

Problem Description

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.

A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.

Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.

Input

The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.

Output

For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.

Sample Input

  
  
   
    
   
   4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0

Sample Output

Source

Zhejiang University Local Contest 2001

Recommend

We have carefully selected several similar problems for you: 1067 1258 1053 1789 1026

Statistic | Submit | Discuss | Note

由于这道题的n最大才为4 所以可以深搜。其实我的第一印象是二分匹配的

没办法喜欢搜索

#include <stdio.h>
#include <string.h>
int n,sum;
char map[10][10];
bool vis[10][10];
//边界检测 
bool limit(int x,int y)
{
	if(x<0||y<0||x>=n||y>=n) return false;
	return true;
}
//检测 
bool check(int x,int y)
{
	//检查第x行
	for(int i=y-1;i>=0;i--)
	{
		if(vis[x][i]) return false;
		if(map[x][i]=='X') break;
	}
	for(int i=y+1;i<n;i++)
	{
		if(vis[x][i]) return false;
		if(map[x][i]=='X') break;
	}
	//检查第y列 
	for(int i=x-1;i>=0;i--)
	if(vis[i][y]||map[i][y]=='X') 
	{
		if(vis[i][y]) return false;
		if(map[i][y]=='X') break;
	}
	for(int i=x+1;i<n;i++)
	{
		if(vis[i][y]) return false;
		if(map[i][y]=='X') break;
	}
	return true;
}
void dfs(int flag,int count)
{
	int x=flag/n,y=flag%n;

//	printf("-%d- ",count);
	if(count>sum) sum=count;
	if(!limit(x,y)) return ;
	
	if(map[x][y]!='X'&&!vis[x][y]&&check(x,y)) 
	{	
		vis[x][y]=true;
	//	printf("%d %d \n",x,y);
		dfs(flag+1,count+1);
	//	printf("\n*******************************\n");
		vis[x][y]=false;
	}
	dfs(flag+1,count);
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(~scanf("%d",&n)&&n)
	{
		memset(vis,false,sizeof(vis));
		memset(map,0,sizeof(map));
		for(int i=0;i<n;i++)
		scanf("%s",map[i]);
		sum=0;
		dfs(0,0);
		printf("%d\n",sum);
	}
	return 0;
}

本文链接：https://blog.csdn.net/su20145104009/article/details/70213486

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

前端开发之vue-grid-layout的使用和实例-程序员宅基地

文章浏览阅读1.1w次，点赞7次，收藏34次。vue-grid-layout的使用、实例、遇到的问题和解决方案_vue-grid-layout

Power Apps-上传附件控件_powerapps点击按钮上传附件-程序员宅基地

文章浏览阅读218次。然后连接一个数据源，就会在下面自动产生一个添加附件的组件。把这个控件复制粘贴到页面里，就可以单独使用来上传了。插入一个“编辑”窗体。_powerapps点击按钮上传附件

C++ 面向对象（Object-Oriented）的特征 & 构造函数& 析构函数_"object(cnofd[\"ofdrender\"])十条"-程序员宅基地

文章浏览阅读264次。(1) Abstraction (抽象)(2) Polymorphism (多态)(3) Inheritance (继承)(4) Encapsulation (封装)_"object(cnofd[\"ofdrender\"])十条"

修改node_modules源码，并保存，使用patch-package打补丁，git提交代码后，所有人可以用到修改后的_修改 node_modules-程序员宅基地

文章浏览阅读133次。删除node_modules，重新npm install看是否成功。在 package.json 文件中的 scripts 中加入。修改你的第三方库的bug等。然后目录会多出一个目录文件。_修改 node_modules

【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure-程序员宅基地

文章浏览阅读883次。【代码】【】kali--password:su的 Authentication failure问题，&sudo passwd root输入密码时Sorry, try again._password: su: authentication failure

整理5个优秀的微信小程序开源项目_微信小程序开源模板-程序员宅基地

文章浏览阅读1w次，点赞13次，收藏97次。整理5个优秀的微信小程序开源项目。收集了微信小程序开发过程中会使用到的资料、问题以及第三方组件库。_微信小程序开源模板

随便推点

Centos7最简搭建NFS服务器_centos7 搭建nfs server-程序员宅基地

文章浏览阅读128次。Centos7最简搭建NFS服务器_centos7 搭建nfs server

Springboot整合Mybatis-Plus使用总结(mybatis 坑补充)_mybaitis-plus ruledataobjectattributemapper' and '-程序员宅基地

文章浏览阅读1.2k次，点赞2次，收藏3次。前言mybatis在持久层框架中还是比较火的，一般项目都是基于ssm。虽然mybatis可以直接在xml中通过SQL语句操作数据库，很是灵活。但正其操作都要通过SQL语句进行，就必须写大量的xml文件，很是麻烦。mybatis-plus就很好的解决了这个问题。..._mybaitis-plus ruledataobjectattributemapper' and 'com.picc.rule.management.d

EECE 1080C / Programming for ECESummer 2022 Laboratory 4: Global Functions Practice_eece1080c-程序员宅基地

文章浏览阅读325次。EECE 1080C / Programming for ECESummer 2022Laboratory 4: Global Functions PracticePlagiarism will not be tolerated:Topics covered:function creation and call statements (emphasis on global functions)Objective:To practice program development b_eece1080c

洛谷p4777 【模板】扩展中国剩余定理-程序员宅基地

文章浏览阅读53次。被同机房早就1年前就学过的东西我现在才学，wtcl。设要求的数为\(x\)。设当前处理到第\(k\)个同余式，设\(M = LCM ^ {k - 1} _ {i - 1}\) ，前\(k - 1\)个的通解就是\(x + i * M\)。那么其实第\(k\)个来说，其实就是求一个\(y\)使得\(x + y * M ≡ a_k(mod b_k)\)转化一下就是\(y * M ...

android 退出应用没有走ondestory方法,[Android基础论]为何Activity退出之后，系统没有调用onDestroy方法？...-程序员宅基地

文章浏览阅读1.3k次。首先，问题是如何出现的？晚上复查代码，发现一个activity没有调用自己的ondestroy方法我表示非常的费解，于是我检查了下代码。发现再finish代码之后接了如下代码finish();System.exit(0);//这就是罪魁祸首为什么这样写会出现问题System.exit(0);////看一下函数的原型public static void exit (int code)//Added ..._android 手动杀死app,activity不执行ondestroy

SylixOS快问快答_select函数导致堆栈溢出 sylixos-程序员宅基地

文章浏览阅读894次。Q: SylixOS 版权是什么形式, 是否分为<开发版税>和<运行时版税>.A: SylixOS 是开源并免费的操作系统, 支持 BSD/GPL 协议(GPL 版本暂未确定). 没有任何的运行时版税. 您可以用她来做任何您喜欢做的项目. 也可以修改 SylixOS 的源代码, 不需要支付任何费用. 当然笔者希望您可以将使用 SylixOS 开发的项目 (不需要开源)或对 SylixOS 源码的修改及时告知笔者.需要指出: SylixOS 本身仅是笔者用来提升自己水平而开发的_select函数导致堆栈溢出 sylixos