是我题目读错了还是我代码写错了
查看原帖
是我题目读错了还是我代码写错了
670584
Zhangikun楼主2023/5/16 23:00

我写了个 O(n3)O(n^3) 的暴力,10pts,请大佬指出哪里思路不对orz

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int sum[105][105],n,m;
int32_t main()
{
  cin>>n>>m;
  for(int i=n;i>=1;i--)
  {
    for(int j=1;j<=m;j++)
    {
      char c;
      cin>>c;
      sum[i][j]=sum[i][j-1];
      if(c=='X')
      {
        sum[i][j]++;
      }
    }
  }
  int ans=1;//不放也算一种
  for(int lt=1;lt<=m;lt++)//左边界
  {
    for(int rt=lt;rt<=m;rt++)//右边界
    {
      for(int i=1;i<=n;i++)//高度
      {
        if(sum[i][rt]-sum[i][lt-1])//这一层不能摆,有不喜欢的地方
        {
          break;
        }
        ans++;
        ans%=mod;
      }
    }
  }
  cout<<ans%mod;
}
2023/5/16 23:00
加载中...