比赛 2024暑假C班集训A 评测结果 AAAAAAAAAT
题目名称 牧场的安排 最终得分 90
用户昵称 彭欣越 运行时间 2.416 s
代码语言 C++ 内存使用 3.37 MiB
提交时间 2024-07-10 10:43:02
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const long long mod=100000000;
int n,m,mk[20][20],mk1[20][20];
long long res=1;
void dfs (int x,int y) {
    //cout << x <<' '<< y <<endl;
    //for (int i=1;i<=n;i++) {
        //for (int j=1;j<=m;j++) {
            //cout << mk[i][j] <<' ';
        //}
        //cout <<endl;
    //}
    for (int i=x;i<=n;i++) {
        for (int j=y;j<=m;j++) {
            if (mk[i][j]==1) {
                res++;
                res%=mod;
                mk[i][j]=0;
                if (i+1<=n) mk[i+1][j]--;
                if (j+1<=m) mk[i][j+1]--;
                if (i-1>0) mk[i-1][j]--;
                if (j-1>0) mk[i][j-1]--;
                dfs(i,j);
                //cout << 1 <<endl;
                mk[i][j]=1;
                if (i+1<=n) mk[i+1][j]++;
                if (j+1<=m) mk[i][j+1]++;
                if (i-1>0) mk[i-1][j]++;
                if (j-1>0) mk[i][j-1]++;
            }
        }
        y=1;
    }
}
int main () {
    freopen("cowfood.in","r",stdin);
    freopen("cowfood.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            cin >> mk[i][j];
            mk1[i][j]=mk[i][j];
        } 
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (mk[i][j]==1) {
                res++;
                res%=mod;
                mk[i][j]=0;
                if (i+1<=n) mk[i+1][j]--;
                if (j+1<=m) mk[i][j+1]--;
                if (i-1>0) mk[i-1][j]--;
                if (j-1>0) mk[i][j-1]--;
                dfs(i,j);
                for (int k=1;k<=n;k++) {
                    for (int v=1;v<=m;v++) {
                        mk[k][v]=mk1[k][v];
                    }
                }
            }
        }
    }
    cout << res <<endl;
    return 0;
}