zoj 1002 Fire Net 碉堡的最大数量【DFS】

题目链接

题目大意：

假设我们有一个正方形的城市，并且街道是直的。城市的地图是n行n列，每一个单元代表一个街道或者一块墙。

碉堡是一个小城堡，有四个开放的射击口。四个方向是面向北、东、南和西。在每一个口子上有一架机关枪。

假设子弹能够穿过任何距离，并且摧毁路上的碉堡。另一方面，子弹不能穿越墙。

我们的目标是在城市里设置足够多的碉堡，并且任何两个碉堡都不会互相摧毁。正确的配置是没有两个碉堡在相同的水平行或者垂直列上，除非碉堡之间有墙把它们分开。在这个问题中，我们将使用小的方形城市（最多4*4），它包含了墙，并且子弹不能穿越。

接下来的图片显示五张城市地图，第1张图片是空的布局，第2张和第3张图片显示了合法的配置，第4和第5张图片显示了非法的配置。对于这样的地形来说，碉堡的最大数是5；第2张图片显示了这个配置方案，但还有其他的配置方案。

你的任务是写一个程序，在给出的地图描述下，计算城市中可以合法放置的碉堡的最大数。

输入文件包含一个或者多个地图描述，0作为文件的结束。每个地图描述首行是城市的尺寸n，n最大为4。接下来的n行描述了地图的每一行，符号“."代表开放区域，大写的X代表墙。输入文件中没有空格。

每一个测试用例，最后输出一行为合法放置碉堡的最大数。

Sample input:

4

.X..

....

XX..

....

2

XX

.X

3

.X.

X.X

.X.

3

...

.XX

.XX

4

....

....

....

....

0

Sample output:

#include <bits/stdc++.h>

using namespace std;

int n,ans;

char mpa[][];

bool vis[][];

bool check(int x,int y){    //四个方向判断是否与之前防止的碉堡冲突

    for(int i=x+;i<=n;i++){ if(mpa[i][y]=='O')return false; if(mpa[i][y]=='X')break; }

    for(int i=x-;i>=;i--){ if(mpa[i][y]=='O')return false; if(mpa[i][y]=='X')break; }

    for(int j=y+;j<=n;j++){ if(mpa[x][j]=='O')return false; if(mpa[x][j]=='X')break; }

    for(int j=y-;j>=;j--){ if(mpa[x][j]=='O')return false; if(mpa[x][j]=='X')break; }

    return true;

}

void dfs(int x,int y,int num){

    if(ans<num)ans=num;

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            if(!vis[i][j]&&check(i,j)&&mpa[i][j]=='.'){

                vis[i][j]=;

                mpa[i][j]='O';

                dfs(i,j,num+);     //选择放与不放

                vis[i][j]=;

                mpa[i][j]='.';

            }

        }

    }

}

int main(){

    while(~scanf("%d",&n),n){

        getchar();

        for(int i=;i<=n;i++){

            scanf("%s",mpa[i]+);

        }

        memset(vis,false,sizeof(vis));

        ans=;

        dfs(,,);

        printf("%d\n",ans);

    }

}

巴特西

zoj 1002 Fire Net 碉堡的最大数量【DFS】

最新文章

热门文章