本文主要是介绍【ACM】HDOJ 1045 Fire Net，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDOJ 1045 Fire Net
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8273 Accepted Submission(s): 4753
题目描述：
一个n*n的地图，请安排blockhouse，要求在同行和同列中没有两个相互连通的blockhouse （障碍物可阻断连通）。如下图中，
第一张图是没有安排blockhouse的图，图中只有墙(wall)
第二和第三张图是合法的blockhouse安排方式
第四和第五张图是不合法的blockhouse安排方式
要求计算出一张图中，最大能安排多少个合法的blockhouse。
输入描述：
可重复输入。
输入一个n，表示地图大小，n≤4。
n为0时结束程序。
“.”表示空白，“X”表示墙。
输出描述：
每个案例一行，表示最大的合法的blockhouse数量。
输入样例：
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0
输出样例：
5
1
5
2
4
我的解法：贪心
么办法最近开始学ACM，才刚刚看到贪心，百度之后发现有DFS和二分查找这两种方法。
我用贪心可是写着太蛋疼了，第一次就WA了，我还以为是算法问题。
经过和AC代码的输出比较我发现，只有当n=1且地图为“X”的时候我的答案和AC答案不一样、整个人瞬间爆炸
因为我用了sort函数：sort(bh,bh+tbh-1,CMP);
那个特例情况中tbh=0，所以末比初要小，直接GG了。
添加一个队tbh的大于0判断，直接AC！！！（— —太蛋疼了）
不过我发现用ProcessDisplay来搞算法很有趣啊，把过程可视化了。有点意思
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
struct Point
{int x;int y;
};
struct Blockhouse
{Point p;int af;
};//ifstream input("F:\\input.txt");
//ofstream output("F:\\output.txt");
char map[4][5];
char PD[6][7];
int n,ans,tbh,tw,//可放blockhouse总数，wall总数tdbh;//已放blockhouse数量，
Point w[16],dbh[16];
Blockhouse bh[16];
/*
void ProcessDisplayFresh()
{system("cls");for(int i=0;i<tdbh;i++){PD[dbh[i].x][dbh[i].y+1]='O';}for(int i=0;i<n;i++){puts(PD[i]);}Sleep(400);
}
*/
int GetRowAf(Point p)
{int a=0;for(int j=p.y+1;j<n;j++)if(map[p.x][j]=='.')a++;elsebreak;for(int j=p.y-1;j>=0;j--)if(map[p.x][j]=='.')a++;elsebreak;return a;
}
int GetColAf(Point p)
{int a=0;for(int i=p.x+1;i<n;i++)if(map[i][p.y]=='.')a++;elsebreak;for(int i=p.x-1;i>=0;i--)if(map[i][p.y]=='.')a++;elsebreak;return a;
}
int isLegal(Point p)
{for(int k=0;k<tdbh;k++){if(p.x==dbh[k].x){//同行int hasWall = 0;for(int i=0;i<tw;i++){if(w[i].x==p.x && (w[i].y - p.y)*(w[i].y - dbh[k].y)<0)hasWall = 1;}if(!hasWall)return false;}else if(p.y==dbh[k].y){//同列int hasWall = 0;for(int i=0;i<tw;i++){if(w[i].y==p.y && (w[i].x - p.x)*(w[i].x - dbh[k].x)<0)hasWall = 1;}if(!hasWall)return false;}}return true;
}
bool CMP(Blockhouse b1,Blockhouse b2)
{return b1.af<b2.af;
}
void acm()
{int i,j;for(i=0;i<n;i++){for(j=0;j<n;j++){if(map[i][j]=='.'){bh[tbh].p= {i,j};bh[tbh].af = GetColAf(bh[tbh].p) + GetRowAf(bh[tbh].p);// printf("---------bh[%d]:(%d,%d),af=%d\n",tbh,bh[tbh].p.x,bh[tbh].p.y,bh[tbh].af);tbh++;}}}if(tbh>0){sort(bh,bh+tbh-1,CMP);dbh[tdbh++]=bh[0].p;// cout<<"第一个，放bh["<<0<<"]：("<<bh[0].p.x<<","<<bh[0].p.y<<")"<<endl;for(i=1;i<tbh;i++){//ProcessDisplayFresh();// printf("尝试放入bh[%d]: (%d,%d),af=%d\n",i,bh[i].p.x,bh[i].p.y,bh[i].af);if(isLegal(bh[i].p)){dbh[tdbh++]=bh[i].p;
// cout<<" 放入bh["<<i<<"]：("<<bh[i].p.x<<","<<bh[i].p.y<<")"<<endl;// ProcessDisplayFresh();}}}ans = tdbh;
// cout<<"work:"<<n<<endl;
}
int main()
{while(cin>>n,n>0){ans=0;tbh=0;tw=0;tdbh=0;for(int i =0;i<n;i++){int j;// PD[i][0]='|';for(j=0;j<n;j++){cin>>map[i][j];if(map[i][j]=='X'){w[tw++] ={i,j};// PD[i][j+1]='X';}else;// PD[i][j+1]=' ';}// PD[i][j+1]='|';// PD[i][j+2]=0;}//算法展示
// ProcessDisplayFresh();//算法内容acm();cout<<ans<<endl;// output<<ans<<endl;}
}这篇关于【ACM】HDOJ 1045 Fire Net的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
