比赛 |
二进制状态表示之搜索中的应用 |
评测结果 |
AAAAAAAA |
题目名称 |
城堡 |
最终得分 |
100 |
用户昵称 |
宇战 |
运行时间 |
0.372 s |
代码语言 |
C++ |
内存使用 |
1.90 MiB |
提交时间 |
2023-07-27 08:36:32 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int vis[100][100],a[100][100],fil[100][100],qq[100][100],ss;
int n,m,s,ans,shu,maxx=0,top;
int op[100][100][5];
struct node{
int x,y,z,p;
}b[100000];
bool cmp(node x,node y){
if(x.p==y.p){
if(x.y==y.y){
return x.x>y.x;
}else{
return x.y<y.y;
}
}else{
return x.p>y.p;
}
}
void init(){
cin>>m>>n;
memset(vis,1,sizeof(vis));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
vis[i][j]=0;
int t=a[i][j],o=0;
for(;t;t>>=1){
o++;
if(t&1){
if(o==1){
op[i][j][1]=1;
}
if(o==2){
op[i][j][2]=1;
}
if(o==3){
op[i][j][3]=1;
}
if(o==4){
op[i][j][4]=1;
}
}
}
}
}
}
void dfs(int x,int y){
if(fil[x][y]==0){
fil[x][y]=ss;
}
if(vis[x][y-1]==0&&op[x][y][1]==0){
vis[x][y-1]=1;
ss++;
dfs(x,y-1);
}
if(vis[x-1][y]==0&&op[x][y][2]==0){
vis[x-1][y]=1;
ss++;
dfs(x-1,y);
}
if(vis[x][y+1]==0&&op[x][y][3]==0){
vis[x][y+1]=1;
ss++;
dfs(x,y+1);
}
if(vis[x+1][y]==0&&op[x][y][4]==0){
vis[x+1][y]=1;
ss++;
dfs(x+1,y);
}
}
void zh(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==0){
ss = 1;
vis[i][j]=1;
dfs(i,j);
}
}
}
memset(vis,1,sizeof(vis));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
vis[i][j]=0;
}
}
}
void mm(){
shu=0,maxx=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(fil[i][j]==1){
shu++;
}
maxx=max(maxx,fil[i][j]);
}
}
memset(fil,0,sizeof(fil));
}
void wall(int x,int y){
if(op[x][y][2]&&x!=1){
op[x][y][2]=0;
op[x-1][y][4]=0;
zh();
mm();
ans=max(ans,maxx);
b[++top].x=x;
b[top].y=y;
b[top].z=2;
b[top].p=maxx;
op[x-1][y][4]=1;
op[x][y][2]=1;
return;
}
if(op[x][y][3]&&y!=m){
op[x][y][3]=0;
op[x][y+1][1]=0;
zh();
mm();
ans=max(ans,maxx);
b[++top].x=x;
b[top].y=y;
b[top].p=maxx;
b[top].z=3;
op[x][y][3]=1;
op[x][y+1][1]=1;
return;
}
}
int main(){
freopen("castle.in","r",stdin);
freopen("castle.out","w",stdout);
init();
zh();
mm();
cout<<shu<<endl<<maxx<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
wall(i,j);
}
}
cout<<ans<<endl;
sort(b+1,b+1+top,cmp);
int pp=1;
cout<<b[pp].x<<' '<<b[pp].y<<' ';
if(b[1].z==2){
cout<<"N";
}else if(b[1].z==3){
cout<<"E";
}
return 0;
}