【算法】算法之美—Fire Net

简介:

题目概述:Fire Net


  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.

  he  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



简单描述

  题是英文的,重要的语句我已经标出来了,其实题的意思很简单:

  在一个n*n(最大为4*4)的矩形表格中,由你指定在哪些表格不空(用"X"表示,代表wall),哪些表格是空的(用"."表示,可以建blockhouses),现在要在空的(".")表格中写O(建blockhouses),要求就是在水平或者竖直方向上不能有两个O直接或间接相邻,问最多可以写几个O(建blockhouses)?



题目分析

  1、不空的表格由自己决定,即为输入的一部分

  2、在水平或者竖直方向上不能有两个O直接或间接相邻,意味着需要作遍历判断

  3、最多可以写几个O(建blockhouses),意味着需要对所有表格进行分析

  下面贴出源代码,其中我对最主要的代码都作了详细的注释



解题算法


 
 
  1. #include < stdio.h>

  2. char map[4][4];

  3. int best,n;

  4. int CanPut(int row, int col)

  5. /*

  6. *检测与前行或者与前列是否存在冲突,即原文中的

  7. *no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them

  8. *如果bullets cannot run through,则返回1

  9. *否则bullets can run through,返回0

  10. */

  11. {

  12. int i;

  13. for (i = row - 1; i >= 0; i--)

  14.   {

  15. if (map[i][col] == 'O') return 0;

  16. if (map[i][col] == 'X') break;

  17.   }

  18. for (i = col - 1; i >= 0; i--)

  19.   {

  20. if (map[row][i] == 'O') return 0;

  21. if (map[row][i] == 'X') break;

  22.   }

  23. return 1;

  24. }

  25. void solve(int k,int tot)

  26. /*

  27. *calculates the maximum number of blockhouses that can be placed in the city in a legal configuration

  28. *k表示被检测的map单元个数

  29. *tot表示可以放置blockhouses的个数

  30. */

  31. {

  32. int x,y;

  33. if(k==n*n)//保证整个地图都被检测过

  34.   {

  35. if(tot>best)  

  36.     {

  37.        best=tot;    

  38. return;  

  39.     }

  40.   }

  41. else

  42.   {

  43.     x=k/n; //先逐行进行检测

  44.     y=k%n; //逐列进行检测

  45. if((map[x][y]=='.') && (CanPut(x,y) ) )//是open space,并且 bullets cannot run through

  46.     {

  47.       map[x][y]='O';//'0'表示已经检测过并且可放置blockhouses,即将tot+1

  48.       solve(k+1,tot+1);//map[x][y]可以放置blockhouses,则从map[(k+1)/n][(k+1)%n]开始继续检测,即逐行进行检测,并且tot+1

  49.       map[x][y]='.';//在恢复堆栈的时候,还原map原来的数据

  50.     }

  51.     solve(k+1,tot);//若map[k/n][k%n]存在bullets can run through,则继续从map[(k+1)/n][(k+1)%n]开始逐行检测

  52.   }

  53. }

  54. int main()

  55. {

  56. int i,j;

  57.   scanf("%d",&n);

  58. while(n>0)

  59.   {

  60. for(i=0;i< n;i++)

  61.     {

  62. for(j=0;j< n;j++)

  63.        {

  64.            scanf("%1s",&map[i][j]);//输入单个字符并且忽略空白

  65.        }

  66.     }

  67.     best=0;

  68.     solve(0,0);

  69.     printf("%d\n",best);

  70.     n=0;//预防scanf失败,reset n

  71.     scanf("%d",&n);

  72.   }

  73. return 0;

  74. }



本文转自infohacker 51CTO博客,原文链接:http://blog.51cto.com/liucw/1194261



相关文章
|
7月前
|
开发框架 算法 搜索推荐
C# .NET面试系列九:常见的算法
#### 1. 求质数 ```c# // 判断一个数是否为质数的方法 public static bool IsPrime(int number) { if (number < 2) { return false; } for (int i = 2; i <= Math.Sqrt(number); i++) { if (number % i == 0) { return false; } } return true; } class Progr
131 1
|
6月前
|
存储 编解码 算法
C#.NET逃逸时间算法生成分形图像的毕业设计完成!晒晒功能
该文介绍了一个使用C#.NET Visual Studio 2008开发的程序,包含错误修复的Julia、Mandelbrot和优化过的Newton三种算法,生成色彩丰富的分形图像。作者改进了原始算法的效率,将内层循环的画点操作移至外部,提升性能。程序提供五种图形模式,支持放大缩小及颜色更新,并允许用户自定义画布大小以调整精度。还具备保存为高质JPG的功能。附有四张示例图片展示生成的分形效果。
|
7月前
|
机器学习/深度学习 编解码 算法
Yolov5改进算法之添加Res2Net模块
Res2Net(Residual Resolution Network)是一种用于图像处理和计算机视觉任务的深度卷积神经网络架构。它旨在解决传统的ResNet(Residual Network)存在的问题,如对不同尺度和分辨率特征的建模不足以及网络深度受限的问题。Res2Net通过引入多分支的结构和逐级增加的分辨率来提高网络的表达能力,从而在各种视觉任务中取得了显著的性能提升。
403 0
|
7月前
|
算法 C#
C# .Net Core bytes转换为GB/MB/KB 算法
C# .Net Core bytes转换为GB/MB/KB 算法
130 0
|
存储 开发框架 算法
ASP.NET Core中使用令牌桶算法限流2
ASP.NET Core中使用令牌桶算法限流2
142 0
|
存储 开发框架 算法
ASP.NET Core中使用令牌桶算法限流1
ASP.NET Core中使用令牌桶算法限流1
86 0
|
存储 开发框架 算法
ASP.NET Core中使用漏桶算法限流
ASP.NET Core中使用漏桶算法限流
102 0
|
机器学习/深度学习 算法 光互联
致敬何凯明的暗通道去雾算法 | NAS-Net: 基于非对齐监督的图像去雾框架
致敬何凯明的暗通道去雾算法 | NAS-Net: 基于非对齐监督的图像去雾框架
356 0
|
算法 安全 开发工具
微软:SHA-1 算法签名的.NET 框架 4 月 26 日将不再支持
微软:SHA-1 算法签名的.NET 框架 4 月 26 日将不再支持
144 0
微软:SHA-1 算法签名的.NET 框架 4 月 26 日将不再支持