Problem Description
Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.)
You can assume that the grass in the board would never burn out and the empty grid would never get fire.
Note that the two grids they choose can be the same.
这个题是要求找到放火的地方，然后能够最快烧完，刚开始想的是用BFS，首先枚举每两个点，然后BFS，10^6的复杂度，可是居然超时了，可能是用的STL，然后就想各种减枝，后来就直接用了Floyd，就是求任意两个点之间的最短距离，然后再枚举每两个点，求出最小值，居然只用了109ms，想不通居然快了10倍以上，复杂度都一样的。。。
代码如下:
#include<iostream> #include<cstring> #include<queue> #include<ctime> #include<cstdio> using namespace std; int map1[15][15]; int rem[15][15]; int N,M; int minans; int cou; int flo[12][12][12][12]; bool judge(int ti,int tj) { if(ti<=0||tj<=0||ti>N||tj>M) return 0; return 1; } void bfs(int si,int sj,int st) { queue <int> que; int temp,ti,tj; que.push(si*100+sj); map1[si][sj]=st; while(!que.empty()) { temp=que.front(); que.pop(); ti=temp/100; tj=temp%100; if(judge(ti-1,tj)&&map1[ti-1][tj]==0) { que.push((ti-1)*100+tj); map1[ti-1][tj]=st; } if(judge(ti+1,tj)&&map1[ti+1][tj]==0) { que.push((ti+1)*100+tj); map1[ti+1][tj]=st; } if(judge(ti,tj-1)&&map1[ti][tj-1]==0) { que.push(ti*100+tj-1); map1[ti][tj-1]=st; } if(judge(ti,tj+1)&&map1[ti][tj+1]==0) { que.push(ti*100+tj+1); map1[ti][tj+1]=st; } } } void floyd() { for(int i1=1;i1<=N;++i1) for(int i2=1;i2<=M;++i2) for(int j1=1;j1<=N;++j1) for(int j2=1;j2<=M;++j2) if(i1==j1&&i2==j2) flo[i1][i2][j1][j2]=0; else if((map1[i1][i2]>0&&map1[j1][j2]>0)&&((i1==j1&&(i2-j2==1||i2-j2==-1))||(i2==j2&&(i1-j1==1||i1-j1==-1)))) flo[i1][i2][j1][j2]=1; else flo[i1][i2][j1][j2]=10e7; for(int k1=1;k1<=N;++k1) for(int k2=1;k2<=M;++k2) if(map1[k1][k2]>0) for(int i1=1;i1<=N;++i1) for(int i2=1;i2<=M;++i2) if(map1[i1][i2]>0) for(int j1=1;j1<=N;++j1) for(int j2=1;j2<=M;++j2) if(map1[j1][j2]>0) flo[i1][i2][j1][j2]=min(flo[i1][i2][j1][j2],flo[i1][i2][k1][k2]+flo[k1][k2][j1][j2]); } int slove() { cou=0; memset(rem,-1,sizeof(rem)); for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) if(map1[i][j]==0) { ++cou; if(cou==3) return -1; bfs(i,j,cou); } int temp,temp1; int maxn=-10e8; minans=10e8; int minn[3]={10e8,10e8,10e8}; if(cou==0) return 0; floyd(); if(cou==2) { for(int i1=1;i1<=N;++i1) for(int i2=1;i2<=M;++i2) if(map1[i1][i2]>0) { maxn=-10e8; for(int j1=1;j1<=N;++j1) for(int j2=1;j2<=M;++j2) if(flo[i1][i2][j1][j2]<10e7&&flo[i1][i2][j1][j2]>maxn) { maxn=flo[i1][i2][j1][j2]; if(maxn>minn[map1[i1][i2]]) goto next1; } next1: if(maxn<minn[map1[i1][i2]]) minn[map1[i1][i2]]=maxn; } return max(minn[1],minn[2]); } else { for(int i1=1;i1<=N;++i1) for(int i2=1;i2<=M;++i2) for(int j1=1;j1<=N;++j1) for(int j2=1;j2<=M;++j2) if(map1[i1][i2]>0&&map1[j1][j2]>0) { maxn=-10e8; for(int k1=1;k1<=N;++k1) for(int k2=1;k2<=M;++k2) if(map1[k1][k2]>0) if(min(flo[i1][i2][k1][k2],flo[j1][j2][k1][k2])>maxn) { maxn=min(flo[i1][i2][k1][k2],flo[j1][j2][k1][k2]); if(maxn>minans) goto next2; } next2: if(maxn<minans) minans=maxn; } return minans; } } int main() { ios::sync_with_stdio(false); int T; char c; int ans; cin>>T; for(int cas=1;cas<=T;++cas) { cin>>N>>M; for(int i=1;i<=N;++i) for(int j=1;j<=M;++j) { cin>>c; if(c=='#') map1[i][j]=0; else map1[i][j]=-1; } ans=slove(); cout<<"Case "<<cas<<": "; if(ans==-1) cout<<-1<<endl; else cout<<ans<<endl; } return 0; }
View Code
转载于:https://www.cnblogs.com/whywhy/p/4229911.html
今天的文章(简单) FZU 2150 Fire Game ，Floyd。分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/30771.html
