`
jackchen0227
  • 浏览: 147229 次
  • 性别: Icon_minigender_1
  • 来自: 帝都
社区版块
存档分类
最新评论

**joj:1017 fire net 递归回溯的使用

    博客分类:
  • ACM
阅读更多

 1017: Fire Net


Result TIME Limit MEMORY Limit Run Times AC Times JUDGE
3s 8192K 1086 565 Standard

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.

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.

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

5
1
5
2
4

 

 

 

/*
	利用回溯的方法来判断所有的可能
*/
#include <stdio.h>
#include <string.h>
int time = 0;
char con[4][4];
int num,Max;
bool check2()
{
	int	i , j;
	for( i = 0 ; i < time ; ++i )
		{
		for( j = 0 ; j < time ; ++j )
			{
			if( con[i][j] == 'f' )
				{
				int	row , col;
				for( row = i + 1 ; row < time && con [row][j] != 'X' ; ++row )
					if( con [row][j] == 'f' )
						return	false;
				for( col = j + 1 ; col < time && con [i][col] != 'X' ; ++col )
					if( con [i][col] == 'f' )
						return	false;
				}
			}
		}
	return	true;
}
void Rec3(int row,int col)	
{
	if(row >= time) //边界之一
	{
		if(num > Max)
			Max = num;
		return;
	}
	if(col >= time) //边界之二
	{		
		Rec3(row +1,0);//col 从0开始
		return ; //这个return 是必须的,要不然回退到此处时候,还会向下执行
	}	
	if(con[row][col] == '.')
	{
		//////////////////////////////////////////////////////////////////////////////////////////
		con[row][col] = 'f';
		num ++;		
		if(check2())		
			 Rec3(row,col + 1); /////////////////////////////////////////////////本区间的代码是回溯可以产生的关键
		num --;
		con[row][col] = '.';
		Rec3(row,col + 1);				
		///////////////////////////////////////////////////////////////////////////////////////////
	}
	else
	{
		Rec3(row,col +1);
	}

}
int main()
{
	memset(con,'\0',sizeof(con));
	freopen("in.txt","r",stdin);
	while(scanf("%d\n",&time) != EOF && time != 0){	
		for(int i=0;i<time;i++)
		{
			for(int j=0;j<time;j++)	
			{
				con[i][j] = (char)getchar();
				if(j == time -1)
					getchar();
			}	
			

				//scanf("%c",&con[i][j]);

		}				
		num = 0;
		Max =0;
		Rec(0,0);
		printf("%d\n",Max);
		
		memset(con,'\0',sizeof(con));
	}
	fclose(stdin);
	return 0;
}
分享到:
评论

相关推荐

    JOJ-jilin-university--acm.rar_joj

    【标题】"JOJ-jilin-university--acm.rar_joj" 提供的是吉林大学JOJ在线判题系统的编程竞赛代码集,主要用于帮助初学者入门。 【描述】中的信息表明,这个压缩包内的代码样例是专门为在JOJ平台上进行编程训练的学生...

    joj上做的一些ACM试题

    【标题】:“JOJ上做的一些ACM试题” 在计算机科学领域,ACM(Association for Computing Machinery)国际大学生程序设计竞赛是一项备受瞩目的比赛,旨在提升大学生的算法设计、问题解决以及团队协作能力。JOJ...

    joj.rar_joj

    这是因为假设最旧的页面不再被频繁使用,因此淘汰它可能导致最小的缺页率。然而,FIFO算法在实际应用中往往表现不佳,因为它容易引发Belady异常,这是一种理论上可能的情况,即增加分配给进程的物理页面数反而导致...

    joj acm 部分习题解答

    【标题】"joj acm 部分习题解答"揭示了这是一份与JOJ(Judge Online Job)和ACM(国际大学生程序设计竞赛)相关的资源,主要是作者对于某些题目的解题思路和代码实现。JOJ是用于在线评测编程竞赛题目的一种平台,而...

    Joj - Java Version of Java-开源

    Java 开源项目 Joj 是一个致力于为 Java ...Joj 的源代码、API 文档以及示例代码通常可在其官方网站或 GitHub 上找到,以便于开发者进一步学习和使用。通过参与开源社区,开发者还可以为项目贡献代码,共同推动其发展。

    安全文明施工管理目标【精选文档】.doc

    4. **现场管理目标**:根据JOJ59—59安全检查标准和重庆市建筑工地文明施工标准,对施工现场进行规范化管理,争取成为重庆市的安全文明施工示范工地。 5. **安全管理目标**: - **安全教育目标**:建立安全生产...

    吉林大学ACM题集.pdf-JOJ

    #### 标题:吉林大学ACM题集.pdf—JOJ 此文档标题明确指出了文档的主要内容——一个由吉林大学组织编写的ACM竞赛题集,并且该题集是以PDF格式提供的。这里提到的“JOJ”即吉林大学在线裁判系统(Jilin University On...

    acm joj 1600

    根据给定的信息,本文将详细解释“acm joj 1600”中的两种大数取模运算方法。此问题主要关注如何高效地计算形如 \(a^b \mod m\) 的表达式,这对于处理大数据或进行密码学运算非常重要。 ### 大数取模运算 #### ...

    joj 部分题目答案 自己做的 仅供参考

    joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考 joj 部分题目答案 自己做的 仅供参考

    acm.rar_acm jlu 10_acm jlu 1029_joj 1237_joj10

    描述中提到的"joj acm 源代码",JOJ(Judge Online Judge)是一个在线编程评测系统,很多高校和编程爱好者使用它来提交和测试代码,解决各种算法问题。源代码通常是程序员编写的原始程序,这里指的可能是参赛者在ACM...

    JoJ-crx插件

    Etre au courant quand JoJ est en live,策划人semaine et liens vers lesréséauxauxsocioaux Soyez au courant纠结JoJ开始à流光! 现场直播将继续进行。 约翰·奎因·伊斯特·布鲁和克林·德集团的非官方网站 D...

    joj 1424 硬币兑换问题

    JOJ 1424题目,即硬币兑换问题,要求参与者通过编程实现一种算法,它能够找到使用最少数量硬币凑成特定金额的方法。动态规划作为一种有效的算法策略,被广泛应用于此类问题的解决之中。 动态规划,简称为DP,是解决...

    吉林大学 joj 1000-2645题代码

    吉林大学 joj 1000-2645题代码,嘿嘿,大家就不用在花JPOINT买代码了,祝ACMer实现自己的心愿

    一个有关调度的问题joj1015

    这个题其实现在想起来也不知道是怎么就给ac的。

    JoJo-s-Bizarre-Survival:一个模组,将JoJo的奇异冒险中的看台添加到Minecraft

    该mod基于荒木飞吕彦的JoJo的奇妙冒险漫画和动漫系列。 这个mod也受到KnightDemon的1.12 mod 极大启发。 这个mod的目的是要从专营权中尽可能多地增加Minecraft,该mod目前仅包含Stand能力,其他能力(Hamon,...

    ControlEstoque_GH:..

    Este Projeto签证是由estoque进行的,它是由mer mercadorias uma determinada empresa sejam averiguadas和atualizadas ... 2021年1月20日,由JoséCláudiodeAraújoJúnior和Annielly Ferreira de Sousa所设计。

    furystudios

    furystudios 普尔维·扎达塔克(Prvi zadatak) ...DroppingOff - radnikhodajućidolazi做pripadajuće科萨雷(izvedeno kroz provjeru tagova kutije)我卡达joj JE dovoljno blizu,fizičkiJE lan

    大智慧最新安装

    大智慧最新安装包,老的已经过期不能查询个人自选股,所以推荐最新的大智慧给大家安装

Global site tag (gtag.js) - Google Analytics