hdu 1045 DFS 建炮台

//x代表墙 . 代表空地 ， 第一行输入n和m表示接下来有一个n*m的地图，现在在空地上放置炮台，判断空地上最多可以放几个炮台，炮台横向和竖向会相互摧毁，但墙可以隔断
//请输出可以放置的最大炮台数目
//Input 4 4
//      .x..
//      ....
//      x...
//      ....
//Output  5
#include<bits/stdc++.h>
using namespace std;

int n,m;
char G[100][100];
char midg[100][100];
int ans;
int temp;

void Init_G()
{
   for(int i=0;i<n;i++)
       for(int j=0;j<m;j++)
           G[i][j]=midg[i][j];
}

//细节啊啊啊啊啊：要注意等于零的边界情况是OK的
bool judge(int x,int y)
{
   if(x<0||y<0||x>n||y>m)
   {
       //超过边界
       return false;
   }
   //判断此这个点是否可以放置炮台
   //向上走：循环结束没有return或者中途break了说明向上走是行得通的
   for(int i=x;i>=0;i--)
   {
       if(G[i][y]=='p')
           return false;//碰到炮台了
       if(G[i][y]=='x')
           break;//碰到墙了
   }
   //向下走
   for(int i=x;i<n;i++)
   {
       if(G[i][y]=='p')
           return false;//碰到炮台了
       if(G[i][y]=='x')
           break;//碰到墙了
   }
   //向左走
   for(int i=y;i>=0;i--)
   {
       if(G[x][i]=='p')
           return false;//碰到炮台了
       if(G[x][i]=='x')
           break;//碰到墙了
   }
   //向右走
   for(int i=y;i<m;i++)
   {
       if(G[x][i]=='p')
           return false;//碰到炮台了
       if(G[x][i]=='x')
           break;//碰到墙了
   }
   //上述四个循环结束可以走到一下这一步说明四面都可以走通
   return true;
}

int shensou(int x,int y)
{
   //一般地图问题都需要坐标的辅助
   //如果是空地并且判断可以放置则放置炮台
   if(G[x][y]=='.'&&judge(x,y)==true)
   {
       G[x][y] = 'p';//放置一个炮台
       temp++;
       //递归深搜
       for(int i=0;i<n;i++)
           for(int j=0;j<m;j++)
           {
               if(G[i][j]=='.'&&judge(i,j)==true)
                   shensou(i,j);
           }
   }
   //最底层层递归返回temp
   return temp;
}

int main()
{
   ans=0;
   scanf("%d%d",&n,&m);
   for(int i=0;i<n;i++)
       for(int j=0;j<m;j++)
       {

           cin>>G[i][j];
           midg[i][j]=G[i][j];
       }
   for(int i=0;i<n;i++)
   {
       for (int j = 0; j < m; j++)
       {
           printf("%c", G[i][j]);
       }
       printf("\n");
   }
   //对图中每一个深搜取最多的炮台数目
   for(int i=0;i<n;i++)
       for(int j=0;j<m;j++)
       {
           temp=0;
           Init_G();//每次深搜都初始化一下图
           //从空地深搜且每次深搜重置此次中间结果
           if(G[i][j]=='.'&& judge(i,j)==true)
           {
               //从没一点开始深搜统计此次深搜的炮台数取最大
               temp=shensou(i,j);
               ans = max(ans,temp);
           }
       }
   cout<<ans;
   return 0;
}