比赛 |
二进制状态表示之搜索中的应用 |
评测结果 |
AAAAAAAA |
题目名称 |
城堡 |
最终得分 |
100 |
用户昵称 |
超人 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2023-07-27 08:36:01 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int a[60][60];
int n,m;
int room, maxn, ans1, ans2, ans3, ans4;
int c[60][60], cnt[3605];
int tmp;
void dfs(int i,int j)
{
if(c[i][j]) return;
tmp++;
c[i][j] = room;
if(!(a[i][j]&1)) dfs(i,j-1);
if(!(a[i][j]&2)) dfs(i-1,j);
if(!(a[i][j]&4)) dfs(i,j+1);
if(!(a[i][j]&8)) dfs(i+1,j);
}
int dx[] = {-1,0};
int dy[] = {0, 1};
void solve()
{
for(int j=1; j<=m; j++)
{
for(int i=n; i>=1; i--)
{
for(int k=0; k<2; k++)
{
if(!(a[i][j]&(1<<(k+1)))) continue;
int ii = i+dx[k];
int jj = j+dy[k];
if(c[i][j] == c[ii][jj]) continue;
if(ii < 1|| ii>n || jj<1 || jj>m) continue;
int temp = cnt[c[i][j]]+cnt[c[ii][jj]];
if(temp > ans1)
{
ans1 = temp;
ans2 = i;
ans3 = j;
ans4 = k;
}
}
}
}
}
int main()
{
freopen("castle.in","r",stdin);
freopen("castle.out","w",stdout);
cin>>m>>n;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
cin>>a[i][j];
}
}
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
if(!c[i][j])
{
room++;
tmp=0;
dfs(i,j);
if(maxn<tmp) maxn=tmp;
cnt[room]=tmp;
}
}
}
cout<<room<<endl<<maxn<<endl;
solve();
cout<<ans1<<endl;
cout<<ans2<<' '<<ans3<<' ';
if(ans4 == 0) cout<<'N'<<endl;
else cout<<'E'<<endl;
return 0;
}