南京理工大学在线oj-1014,请问这道题用C++该怎么写

问题描述：

问题：
当下，全国各地安全事故时有发生。各大高校对此很是重视。于是，高校安全设施也相应的增加了。其中摄像头的安装对安全稳定的重要性不言而喻。简而言之，为了实时监控某个区域的状况，我们要在某些区域安装摄像头。
为了使问题简单化，将某个区域看成是有若干方格组成的正方形，每堵墙占一个方格，墙会阻碍摄像头的摄像。也许是各大高校过于紧张，他们觉得安装的摄像头越多越好，然而他们又不希望过于浪费（即不希望两个或多个摄像头出现在同一行或同一列）。当然大前提是监控整个区域。请你帮忙找出可以安装的最大摄像头数。（可以假设，每个摄像头只能监控它所在方格的列和行）。

Input
有多个用例直到文件结尾
每个用例的形式如下：
第一行：n分别表示矩形方格的行数和列数（1<=n<=4）
以下为n*n矩阵。用 “.” 表示空的区域，用“X”表示墙。

Output
一个整数，表示所要安装的最大摄像头数。

Sample Input
4
....
....
....
....
4
.X..
....
XX..
....

Sample Output
4
5

答

利用回溯法，具体代码如下：

#include<stdio.h>
#include<iostream>
using namespace std;

#define MAX 4    //n的最大值为4

void search(int m,int n,int &maxcount,int Res[],int Data[][MAX]); //回溯法求解
int CanPlace(int m,int n,int Res[],int Data[][MAX]);    //判断在m位置处能不能放摄像头
void CheckResult(int n,int &maxcount,int Res[]);    //更新结果

int main()
{
    int i = 0,j = 0,n = 0;   //矩形方格行列数
    int maxcount = 0;        //保存最终结果
    int Data[MAX][MAX];      //存储区域信息，0代表空格，1代表墙
    int Res[MAX*MAX] = {0};  //存储放摄像头位置
    char c;

    while(cin>>n)      //文档尾结束
    {
        fflush(stdin);
        maxcount = 0;
        for(i = 0; i < n; i++)        //读取数据
        {
            for(j = 0; j < n; j++)
            {
                cin>>c;
                if(c == 'X' || c == 'x')    //墙
                {
                    Data[i][j] = 1;
                }
                else if(c == '.')           //空格
                {
                    Data[i][j] = 0;
                }
                else                       //其余情况
                {
                    Data[i][j] = 0;
                }
            }
            fflush(stdin);
        }
        search(0,n,maxcount,Res,Data);
        cout<<maxcount<<endl;              //输出结果
    }
}

void search(int m,int n,int &maxcount,int Res[],int Data[][MAX]) //回溯法求解
{
    if(m == n*n)    //回溯结束条件
    {
        CheckResult(n,maxcount,Res);
        return;
    }
    else         //继续回溯
    {
        Res[m] = 0;      //不放摄像头，递归搜索
        search(m+1,n,maxcount,Res,Data);
        if(CanPlace(m,n,Res,Data))   //放摄像头，递归搜索
        {
            Res[m] = 1;
            search(m+1,n,maxcount,Res,Data);
        }
    }
}

int CanPlace(int m,int n,int Res[],int Data[][MAX])    //判断在m位置处能不能放摄像头
{
    int i=0,j=0,row=0,col=0,flag1=0,flag2=0,flag=0;
    row=m/n;      //m处所对应的行
    col=m%n;      //m处所对应的列
    i=row-1;
    j=col-1;
    if(Data[row][col]==1)return 0;      //有墙不能放
    while(i>=0)
    {
        if(Data[i][col]==1)    //在这一列上有墙
        {
            flag1=1;
            break;
        }
        if(Res[i*n+col]==1)    //这一列已经放过摄像头
        {
            flag1=0;
            break;
        }
        i--;
    }
    if(i<0)flag1=1;
    while(j>=0)
    {
        if(Data[row][j]==1)    //在这一行上有墙
        {
            flag2=1;
            break;
        }
        if(Res[row*n+j]==1)    //这一行已经放过摄像头
        {
            flag2=0;
            break;
        }
        j--;
    }
    if(j<0)flag2=1;
    flag=flag1*flag2;         //两个条件同时为1，才可以放摄像头
    return flag;
}

void CheckResult(int n,int &maxcount,int Res[])    //更新结果
{
    int i=0,count=0;
    for(i=0;i<n*n;i++)
    {
        count=count+Res[i];      //可放的摄像头数量
    }
    if(count>maxcount)maxcount=count;    //更新最大值
}

南京理工大学在线oj-1014,请问这道题用C++该怎么写

相关推荐