首页 > 代码库 > hdu1045 DFS
hdu1045 DFS
#include<stdio.h>#include<string.h>int n;int maxx;char map[5][5];int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};int block[16][5][5];//炮台位置bool ok(int x,int y){ int i,x1,y1; if(map[x][y]!=‘.‘) return false; for(i=0;i<4;i++){ x1=x+dx[i]; y1=y+dy[i]; while(1){ if(x1<0||x1>=n||y1<0||y1>=n||map[x1][y1]==‘X‘)//遇到边界跳出来 break; else if(map[x1][y1]==‘1‘)//遇到‘X‘跳出来 return false; x1+=dx[i]; y1+=dy[i];//没有的话就沿着行和列一直找 } } return true;}void dfs(int k){ int i,j; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(ok(i,j)){//判断是否能放置 map[i][j]=‘1‘;//如果能将其所在行和列标记为‘1‘,不能放置直到碰到‘X‘ dfs(k+1);//成功放置的话就加1 map[i][j]=‘.‘;//回溯 } } if(maxx<k){//寻找最大数量 maxx=k; } }}int main(){ int i,j; while(scanf("%d",&n)!=EOF&&n){ maxx=0; for(i=0;i<n;i++){ scanf("%s",map[i]); } dfs(0); printf("%d\n",maxx); } return 0;}
hdu1045 DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。