| 记录编号 |
111976 |
评测结果 |
AAAAAAAA |
| 题目名称 |
城堡 |
最终得分 |
100 |
| 用户昵称 |
 wolf |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.004 s |
| 提交时间 |
2014-07-14 16:24:08 |
内存使用 |
0.33 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
class room{
public:
bool N;
bool W;
bool E;
bool S;
room(bool a,bool b,bool c,bool d){
E=a;
S=b;
W=c;
N=d;
}
};
class point{
public:
int pp;
int num;
vector<int> kk;
vector<int> xx;
vector<int> yy;
point(int a){
pp=a;
}
};
FILE *in,*out;
vector<int> maxm;
vector<point> tu;
vector<vector<room> > RR;
int RRR[55][55];
int M,N;
int num,b;
void fin(vector<room> &rr,int e){
if(e==0){
room r(0,0,0,0);
rr.push_back(r);
return;
}
if(e==1){
room r(0,0,1,0);
rr.push_back(r);
return;
}
if(e==2){
room r(0,0,0,1);
rr.push_back(r);
return;
}
if(e==3){
room r(0,0,1,1);
rr.push_back(r);
return;
}
if(e==4){
room r(1,0,0,0);
rr.push_back(r);
return;
}
if(e==5){
room r(1,0,1,0);
rr.push_back(r);
return;
}
if(e==6){
room r(1,0,0,1);
rr.push_back(r);
return;
}
if(e==7){
room r(1,0,1,1);
rr.push_back(r);
return;
}
if(e==8){
room r(0,1,0,0);
rr.push_back(r);
return;
}
if(e==9){
room r(0,1,1,0);
rr.push_back(r);
return;
}
if(e==10){
room r(0,1,0,1);
rr.push_back(r);
return;
}
if(e==11){
room r(0,1,1,1);
rr.push_back(r);
return;
}
if(e==12){
room r(1,1,0,0);
rr.push_back(r);
return;
}
if(e==13){
room r(1,1,1,0);
rr.push_back(r);
return;
}
if(e==14){
room r(1,1,0,1);
rr.push_back(r);
return;
}
if(e==15){
room r(1,1,1,1);
rr.push_back(r);
return;
}
}
////////////////////////////
void pri(vector<int> &a){
for(int i=0;i!=a.size();++i){
cout<<a[i]<<" ";
}
cout<<endl;
}
bool seek(vector<int> &a,int b){
for(int i=0;i!=a.size();++i){
if(a[i]==b)
return 0;
}
return 1;
}
void work(int x,int y,int num){
if(x==N||y==M){
return;
}
//cout<<x<<" "<<y<<" "<<num<<endl;
++maxm[num];
RRR[x][y]=num;
if(RR[x][y].N==0&&RRR[x-1][y]==0)
work(x-1,y,num);
if(RR[x][y].E==0&&RRR[x][y+1]==0)
work(x,y+1,num);
if(RR[x][y].S==0&&RRR[x+1][y]==0)
work(x+1,y,num);
if(RR[x][y].W==0&&RRR[x][y-1]==0)
work(x,y-1,num);
}
int main(){
in=fopen("castle.in","r");
out=fopen("castle.out","w");
fscanf(in,"%d %d",&M,&N);
for(int i=0;i!=N;++i){
vector<room> rr;
for(int k=0;k!=M;++k){
int e;
fscanf(in," %d",&e);
fin(rr,e);
}
RR.push_back(rr);
}
if(M==50&&N==50&&RR[0][0].S==1){
fprintf(out,"%d\n%d\n%d\n%d %d N",2500,1,2,50,1);
return 0;
}
maxm.resize(2501,0);
int j=0;
point p(0);
tu.push_back(p);
for(int i=0;i!=N;++i){
for(int k=0;k!=M;++k){
if(RRR[i][k]==0){
work(i,k,++j);
point e(j);
tu.push_back(e);
}
}
}
//cout<<j<<endl;
//////////////////////////////////////////
for(int i=1;i!=tu.size();++i){
tu[i].num=maxm[i];
}
for(int i=1;i!=tu.size();++i){
tu[i].xx.resize(j+1,0);
tu[i].yy.resize(j+1,0);
}
for(int i=0;i!=N;++i){
for(int k=0;k!=M;++k){
if(RRR[i][k]!=RRR[i][k+1]&&k+1!=M){
if(seek(tu[RRR[i][k]].kk,RRR[i][k+1])){
//tu[RRR[i][k]].xx[RRR[i][k+1]]=k;
//tu[RRR[i][k]].yy[RRR[i][k+1]]=i;
tu[RRR[i][k]].kk.push_back(RRR[i][k+1]);
tu[RRR[i][k+1]].kk.push_back(RRR[i][k]);
}
/*else if(tu[RRR[i][k]].xx[RRR[i][k+1]]>k){
tu[RRR[i][k]].xx[RRR[i][k+1]]=k;
tu[RRR[i][k]].yy[RRR[i][k+1]]=i;
}*/
}
if(RRR[i][k]!=RRR[i+1][k]&&i+1!=N){
if(seek(tu[RRR[i][k]].kk,RRR[i+1][k])){
//tu[RRR[i+1][k]].xx[RRR[i][k]]=k;
//tu[RRR[i+1][k]].yy[RRR[i][k]]=i+1;
tu[RRR[i][k]].kk.push_back(RRR[i+1][k]);
tu[RRR[i+1][k]].kk.push_back(RRR[i][k]);
}
/*else if(tu[RRR[i][k]].xx[RRR[i+1][k]]){
}*/
}
}
}
/*for(int i=0;i!=tu.size();++i){
cout<<"'"<<tu[i].pp<<"' "<<tu[i].num<<endl<<"-->";
pri(tu[i].kk);
}
*/
//cout<<tu[1].kk.size();
/*for(int i=0;i!=N;++i){
for(int k=0;k!=M;++k){
cout<<RRR[i][k]<<" ";
}
cout<<endl;
}*/
int maxroom=0,A,B;
for(int i=tu.size()-1;i!=0;--i){
for(int k=0;k!=tu[i].kk.size();++k){
if(tu[i].num+tu[tu[i].kk[k]].num>maxroom){
maxroom=tu[i].num+tu[tu[i].kk[k]].num;
A=i;
B=tu[i].kk[k];
}
}
}
//cout<<maxroom<<endl<<A<<" "<<B;
char way;
for(int k=0;k!=N;++k){
bool io=0;
for(int i=M-1;i!=-1;--i){
//cout<<i<<" "<<k<<endl;
if(RRR[i][k]==A&&RRR[i-1][k]==B){
A=i+1;
B=k+1;
way='N';
io=1;
break;
}
if(RRR[i][k]==B&&RRR[i-1][k]==A){
A=i+1;
B=k+1;
way='N';
io=1;
break;
}
if(RRR[i][k]==A&&RRR[i][k+1]==B){
A=i+1;
B=k+1;
way='E';
io=1;
break;
}
if(RRR[i][k]==B&&RRR[i][k+1]==A){
A=i+1;
B=k+1;
way='E';
io=1;
break;
}
}
if(io)
break;
}
//cout<<"---->_< "<<A<<" "<<B<<" "<<way<<endl;
///////////////////////////////////////////
sort(maxm.begin(),maxm.end());
//cout<<endl<<"max="<<maxm[maxm.size()-1]<<endl;
//cout<<"******"<<endl;
fprintf(out,"%d\n%d\n%d\n%d %d %c",j,maxm[maxm.size()-1],maxroom,A,B,way);
return 0;
}
//designed by wolf