hdu 1045 Fire Net dfs

本文主要是介绍hdu 1045 Fire Net dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1045

深搜。在find()函数找上下左右是否有碉堡的时候，要从x-1和y-1为起点开始搜。如果从0为起点开始搜 则错误。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cctype>
using namespace std;
int n,tmp;
char a[4][4];
bool find(int x,int y)
{for(int i =x-1;i>=0;i--){if(a[i][y] == 'O')return false;if(a[i][y] == 'X')break;}for(int i= y-1;i>= 0;i--){if(a[x][i] == 'O')return false;if(a[x][i] == 'X')break;}return true ;
}
void dfs(int k,int current)
{int x,y;if(k == n*n){if(current > tmp){tmp = current;return ;}}else{x=k/n;y=k%n;if(a[x][y]== '.'&&find(x,y)){a[x][y]='O';dfs(k+1,current+1);a[x][y]='.';}dfs(k+1,current);}
}
int main()
{while(cin>>n){if(n == 0)break;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];tmp=0;dfs(0,0);cout<<tmp<<endl;}
}

这篇关于hdu 1045 Fire Net dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---