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; }