题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1045

题目描述： 在矩阵中放车，车可四面攻击，矩阵中有墙，可以防止攻击，给出墙的位置，输出最多可以放多少车；

题目要点：dfs&二分图最大匹配（匈牙利算法）（这里是dfs）

   本题在一开始作的时候陷入了贪心的漩涡，写出来的以为是dfs、但实际上是谈心，而且贪心在这里是错误的；（贪心算法的应用范围比较窄，多数情况下是错误的）

然后发现了dfs与贪心的不同；贪心算法是每次放置车的方法都是固定，实际上并没有列举出所有的情况；dfs算法还是构建树，对于一个点，当不能放在这里的时候就dfs、他的下一个点，如果可以放在这里，并不是一定就要放在这里（这一点是和贪心算法区别最大的地方，谈心算法就是如果这里能放那就放这样影响了后面的防止情况，所以并没有列举出全部的情况），可以选择放，或者不放，如果放，就改变一下该点的状态，然后dfs下一个点，并在dfs结束时还原现场，即将状态改回来；如果选择不放就直接dfs下一个点（dfs的顺序是从上到下从左到右，如果跑到最右下角就结束）；

代码如下：

 

1 #include
      
        2 #include
       
         3 using namespace std; 4 char a[6][6]; 5 int maxn=0,n; 6 bool check(int x,int y)//检查该点是否可以放； 7 { 8     for(int i=x-1;i>=0;i--) 9     {10         if(a[i][y]=='X')11             break;12         if(a[i][y]=='*')13                 return false;14     }15     for(int i=y-1;i>=0;i--)16     {17         if(a[x][i]=='X')18             break;19         if(a[x][i]=='*')20             return false;21     }22     return true;23 }24 void dfs(int x,int y,int count)25 {26     if(x>=n)27         {28             if(maxn
        
         =n)33     {34         dfs(x+1,0,count);35     }36     else37     {38         if(a[x][y]=='.'&&check(x,y))39         {40             a[x][y]='*';//修改现场；41             dfs(x,y+1,count+1);42             a[x][y]='.';//还原现场；43         }44         dfs(x,y+1,count);//这个地方是这个点不放的时候的情况；（及时可以放也要考虑不放的情况:）；45     }46 }47 int main()48     {49     while(cin>>n&&n)50     {51         for(int i=0;i