HDU 1045-Fire Net

题意链接

题目分析

题意

在n*n的地图上放置大炮（n最大为4），避免互相攻击不能将其放在同一行，不能在同一列，但墙可以阻隔攻击，求最多能放置的数量。

思路

优先放置影响范围小的大炮。

代码

#include<stdio.h> #include<string.h> #define INF 8 char map[5][5]; int a[5][5]; int main(){ //freopen("TXA.txt","r",stdin); int n; while(~scanf("%d",&n),n){ int res=0; int i,j,k; memset(map,0,sizeof(map)); memset(a,0,sizeof(a)); for(i=0;i<n;i++) scanf("%s",map[i]);//输入每一行 for(i=0;i<n;i++)//找出各个空地安置大炮后的影响范围大小 for(j=0;j<n;j++) if(map[i][j]=='.'){ for(k=i-1;k>=0&&map[k][j]=='.';k--) a[i][j]++; for(k=i+1;k<n&&map[k][j]=='.';k++) a[i][j]++; for(k=j-1;k>=0&&map[i][k]=='.';k--) a[i][j]++; for(k=j+1;k<n&&map[i][k]=='.';k++) a[i][j]++; a[i][j]++; } for(i=0;i<n;i++){ int min=INF,ii,jj; for(j=0;j<n;j++)//求出i行影响范围最小的放置位置 if(a[i][j]>0&&min>a[i][j]){ min=a[i][j]; ii=i; jj=j; } if(min!=INF){//将i行求出的放置位置影响范围标记 res++; for(k=ii-1;k>=0&&map[k][jj]=='.';k--) a[k][jj]=INF; for(k=ii+1;k<n&&map[k][jj]=='.';k++) a[k][jj]=INF; for(k=jj-1;k>=0&&map[ii][k]=='.';k--) a[ii][k]=INF; for(k=jj+1;k<n&&map[ii][k]=='.';k++) a[ii][k]=INF; a[ii][jj]=INF; i--;//防漏 } } printf("%d\n",res); } return 0; }