看到题目介绍我就虚了，看到问题我更虚了，结果写了堆又臭又长的代码，提交了几次，改了几个错误，想着最后肯定超时，没想到竟然过了...
1 /* 2 ID: hubiao cave 3 PROG: castle 4 LANG: C++ 5 */ 6 7 8 #include <iostream> 9 #include <fstream> 10 #include <cstring> 11 #include <set> 12 #include <deque> 13 #include <algorithm> 14 using namespace std; 15 16 #define EDGE 9999 17 18 struct ROOM 19 { 20 int wnes[4]; 21 ROOM() 22 { 23 memset(wnes,0,4*4); 24 } 25 }; 26 27 struct WALL 28 { 29 int row; 30 int col; 31 char ch; 32 }; 33 34 struct TWOPTR 35 { 36 set<int>*p1; 37 set<int>*p2; 38 }; 39 40 ROOM rooms[2502]; 41 bool visited[2502]={0}; 42 43 void restore(int row,int column,ifstream* fin); 44 void dfs(int,set<int>*); 45 46 bool lesssize(set<int>*, set<int>*); 47 bool canmerge(set<int>*,set<int>*); 48 bool operator < (const WALL&,const WALL&); 49 50 51 ifstream* pfin; 52 deque<set<int>* >liset; 53 set<WALL> sw; 54 deque<TWOPTR> dt; 55 56 int grow,gcolumn; 57 58 59 int main() 60 { 61 pfin=new ifstream("castle.in"); 62 ofstream fout("castle.out"); 63 64 int row,column; 65 int count=0; 66 *pfin>>column>>row; 67 grow=row; 68 gcolumn=column; 69 70 restore(row,column,pfin); 71 for(int i=1;i<=row*column;i++) 72 { 73 if(!visited[i]) 74 { 75 set<int>*pset=new set<int>; 76 dfs(i,pset); 77 liset.push_back(pset); 78 count++; 79 } 80 } 81 fout<<count<<endl; 82 int maxsize=0; 83 for(deque<set<int>*>::iterator it=liset.begin();it!=liset.end();it++) 84 { 85 if((*it)->size()>maxsize) 86 { 87 maxsize=(*it)->size(); 88 } 89 90 } 91 fout<<maxsize<<endl; 92 sort(liset.begin(),liset.end(),lesssize); 93 94 95 set<int>*p1,*p2; 96 int maxsum=0; 97 for(int i=liset.size()-1;i>=0;i--) 98 { 99 100 for(int j=i-1;j>=0;j--) 101 { 102 if(canmerge(liset[j],liset[i])) 103 { 104 105 if(maxsum==liset[j]->size()+liset[i]->size()) 106 { 107 TWOPTR tp; 108 tp.p1=liset[j]; 109 tp.p2=liset[i]; 110 dt.push_back(tp); 111 } 112 if(maxsum<liset[j]->size()+liset[i]->size()) 113 { 114 p1=liset[j]; 115 p2=liset[i]; 116 TWOPTR tp; 117 tp.p1=p1; 118 tp.p2=p2; 119 dt.clear(); 120 dt.push_back(tp); 121 maxsum=liset[j]->size()+liset[i]->size(); 122 } 123 124 125 } 126 127 } 128 129 } 130 fout<<maxsum<<endl; 131 132 for(deque<TWOPTR>::iterator it=dt.begin();it!=dt.end();it++) 133 { 134 p1=(*it).p1; 135 p2=(*it).p2; 136 137 138 for(set<int>::iterator it=p1->begin();it!=p1->end();it++) 139 { 140 int number=*it; 141 if(number%gcolumn!=1) 142 { 143 if(p2->count(number-1)) 144 { 145 WALL wa; 146 if(number%column!=0) 147 wa.row=number/column+1; 148 else 149 wa.row=number/column; 150 if(number%column!=0) 151 wa.col=number%column-1; 152 else 153 wa.col=column-1; 154 155 wa.ch='E'; 156 sw.insert(wa); 157 } 158 159 } 160 if(number>gcolumn) 161 { 162 if(p2->count(number-gcolumn)) 163 { 164 WALL wa; 165 if(number%column!=0) 166 wa.row=number/column+1; 167 else 168 wa.row=number/column; 169 if(number%column!=0) 170 wa.col=number%column; 171 else 172 wa.col=column; 173 wa.ch='N'; 174 sw.insert(wa); 175 } 176 177 } 178 if(number%gcolumn!=0) 179 { 180 if(p2->count(number+1)) 181 { 182 WALL wa; 183 wa.row=number/column+1; 184 wa.col=number%column; 185 wa.ch='E'; 186 sw.insert(wa); 187 } 188 } 189 if(number<=(grow-1)*gcolumn) 190 { 191 if(p2->count(number+gcolumn)) 192 { 193 WALL wa; 194 if(number%column!=0) 195 wa.row=number/column+2; 196 else 197 wa.row=number/column+1; 198 if(number%column!=0) 199 wa.col=number%column; 200 else 201 wa.col=column; 202 wa.ch='N'; 203 sw.insert(wa); 204 } 205 } 206 } 207 } 208 fout<<(*sw.begin()).row<<" "<<(*sw.begin()).col<<" "<<(*sw.begin()).ch<<endl; 209 210 return 0; 211 } 212 213 void restore(int row,int column,ifstream* fin) 214 { 215 for(int i=1;i<=row;i++) 216 for(int j=1;j<=column;j++) 217 { 218 int t; 219 *fin>>t; 220 221 if(!(t&1))//西面没墙 222 { 223 if(j!=1) 224 rooms[(i-1)*column+j].wnes[0]=(i-1)*column+j-1; 225 else 226 rooms[(i-1)*column+j].wnes[0]=EDGE; 227 } 228 229 if(!(t&2)) 230 { 231 if(i!=1) 232 rooms[(i-1)*column+j].wnes[1]=(i-2)*column+j; 233 else 234 rooms[(i-1)*column+j].wnes[1]=EDGE; 235 236 } 237 if(!(t&4)) 238 { 239 if(j!=column) 240 rooms[(i-1)*column+j].wnes[2]=(i-1)*column+j+1; 241 else 242 rooms[(i-1)*column+j].wnes[2]=EDGE; 243 } 244 if(!(t&8)) 245 { 246 if(i!=row) 247 rooms[(i-1)*column+j].wnes[3]=i*column+j; 248 else 249 rooms[(i-1)*column+j].wnes[3]=EDGE; 250 } 251 } 252 } 253 void dfs(int index,set<int>* pset) 254 { 255 256 if(!visited[index]) 257 { 258 visited[index]=1; 259 pset->insert(index); 260 for(int i=0;i<4;i++) 261 { 262 if(rooms[index].wnes[i]!=0&&rooms[index].wnes[i]!=EDGE) 263 { 264 dfs(rooms[index].wnes[i],pset); 265 } 266 } 267 } 268 else 269 return; 270 } 271 bool lesssize( set<int>* s1, set<int>* s2) 272 { 273 return s1->size()<s2->size(); 274 } 275 bool canmerge(set<int>* s1,set<int>* s2) 276 { 277 for(set<int>::iterator it=s1->begin();it!=s1->end();it++) 278 { 279 int number=*it; 280 if(number%gcolumn!=1) 281 { 282 if(s2->count(number-1)) 283 return true; 284 } 285 if(number>gcolumn) 286 { 287 if(s2->count(number-gcolumn)) 288 return true; 289 } 290 if(number%gcolumn!=0) 291 { 292 if(s2->count(number+1)) 293 return true; 294 } 295 if(number<=(grow-1)*gcolumn) 296 { 297 if(s2->count(number+gcolumn)) 298 return true; 299 } 300 } 301 return false; 302 } 303 bool operator < (const WALL& w1,const WALL& w2) 304 { 305 if(w1.col!=w2.col) 306 return w1.col<w2.col; 307 if(w1.row!=w2.row) 308 return w1.row>w2.row; 309 return w1.ch>w2.ch; 310 311 }