比赛 二进制状态表示之搜索中的应用 评测结果 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;
}