首页 > 代码库 > 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