攝像頭-南京理工大學在線oj-1014,請問這道題用C++該怎麼寫

南京理工大學在線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;    //更新最大值
}