2 条题解

  • 1
    @ 2025-9-22 20:38:05
    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N=1e3+10;
    const int INF=0x3f3f3f3f;
    inline int read(){ll x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;}
    ll n,m,cnt,dx[4]={1,-1,0,0},dy[4]={0,0,-1,1},sum,ans;
    char a[N][N];
    bool check(ll x,ll y){
        for(int i=0;i<4;i++){
            ll xx=x+dx[i],yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]=='#'){
            	return 0;
    		}
        }
        return 1;
    }
    int main(){
    	//freopen(".in","r",stdin);
    	//freopen(".out","w",stdout);
        cin>>n>>m;
        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(a[i][j]=='.'&&check(i,j)){
            		cnt++;
    			}
    			else if(a[i][j]=='#'){
                    a[i][j]='.';
                    sum=0;
                    if(check(i,j)){
                    	sum++;
    				}
                    for(int k=0;k<4;k++){
                        ll xx=i+dx[k],yy=j+dy[k];
                        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]=='.'&&check(xx,yy)){
                        	sum++;
    					}
                    }
    				a[i][j]='#';
                }
                ans=max(ans,sum);
        	}
    	}
        cout<<ans+cnt;
    }
    
    
    • 0
      @ 2025-9-23 15:30:17
      #include <iostream>
      #include <vector>
      #include <string>
      using namespace std;
      inline bool in(int x, int y, int n, int m) {
          return x >= 0 && x < n && y >= 0 && y < m;
      }
      inline bool good(const vector<string>& g, int x, int y, int n, int m) {
          const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
          for (int i = 0; i < 4; i++) {
              int nx = x + d[i][0], ny = y + d[i][1];
              if (in(nx, ny, n, m) && g[nx][ny] == '#')
                  return false;
          }
          return true;
      }
      inline bool goodAfter(const vector<string>& g, int x, int y, int cx, int cy, int n, int m) {
          const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
          for (int i = 0; i < 4; i++) {
              int nx = x + d[i][0], ny = y + d[i][1];
              if ((nx == cx && ny == cy) || !in(nx, ny, n, m))
                  continue;
              if (g[nx][ny] == '#')
                  return false;
          }
          return true;
      }
      
      int main() {
          int n, m;
          cin >> n >> m;
          vector<string> g(n);
          for (int i = 0; i < n; i++) cin >> g[i];
          int orig = 0;
          for (int i = 0; i < n; i++)
              for (int j = 0; j < m; j++)
                  if (g[i][j] == '.' && good(g, i, j, n, m))
                      orig++;
          
          int maxAdd = 0;
          const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
          for (int i = 0; i < n; i++) {
              for (int j = 0; j < m; j++) {
                  if (g[i][j] == '#') {
                      int add = 0;
                      if (goodAfter(g, i, j, i, j, n, m)) add++;
                      for (int k = 0; k < 4; k++) {
                          int x = i + d[k][0], y = j + d[k][1];
                          if (in(x, y, n, m) && g[x][y] == '.') {
                              if (!good(g, x, y, n, m) && goodAfter(g, x, y, i, j, n, m))
                                  add++;
                          }
                      }
                      maxAdd = max(maxAdd, add);
                  }
              }
          }
          
          cout << orig + maxAdd << endl;
          return 0;
      }
          
      
      
      • 1

      信息

      ID
      3314
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      递交数
      93
      已通过
      15
      上传者