代码未通过所有测试用例

Question

我试图解决以下问题：

您正在玩一个游戏，其中有一个由 nn 个单元格组成的矩形网格。每个单元格要么是空的，要么有烟花。空单元格标有“.”，带有烟花的单元格标有“”。如果两个单元格共享一条边，则称它们相邻。

如果烟花在任何单元格中爆炸，它会破坏自身以及与之相连的空单元格。如果两个单元格之间存在空的相邻单元格路径，则两个单元格相连。如果单独触发烟花，您必须找到将被摧毁的细胞数量。输入约束： 1≤n≤1000 样本输入 4

* 。 . *

。 . * .

* 。 . *

示例输出 66(9(第 1 个 *)+10+10+9+10+9+9(第 7 个 *)).

我的代码：

#include <iostream>
#include <queue>
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <cstdio>
#define n 1001
using namespace std;
///char arr[1001][1001];
bool is_valid(int x,int y,int n1){
    if(x<0||y<0||x>=n1||y>=n1){
        return false;
    }
    return true;
}
int cal_(int i,int j,char arr[n][n],int n1){
    pair<int,int> p(i,j);
    queue<pair<int,int> > q;
    //for()
    q.push(p);
    int ans_ = 0;
    //visited
    bool visited[n1][n1] = {{0}};
    //visited[][]
    int diff[][2] = {{-1,0},{0,1},{1,0},{0,-1}};
    while(!q.empty()){
        pair<int,int> curr = q.front();
        q.pop();
        int x = curr.first;
        int y = curr.second;
        //cout<<"x and y"<<x<<" "<<y<<endl;
        visited[x][y] = 1;
        for(int k=0;k< 4;k++){
            int newx = x + diff[k][0];
            int newy = y + diff[k][1];
            //cout<<newx<<" "<<newy<<" arr->"<<" "<<arr[newx][newy]<<endl;
            if(is_valid(newx,newy,n1)){
                    if( arr[newx][newy] == '.' && visited[newx][newy] == 0){
                        visited[newx][newy] = 1;
                        //cout<<newx<<" "<<newy<<endl;
                        ans_++;
                        pair<int,int> p(newx,newy);
                        q.push(p);
                    }
            }
        }
    }
    //cout<<ans_+1<<endl;
    //if(ans_!=0)
        return ans_+1;
    //else
      //  return 0;
}
int main(){
    //cout << "Hello World!" << endl;
    std::ios::sync_with_stdio(false);
    int n1;
    //char arr[n][n];
    //char arr_copy[n][n];
    cin>>n1;
//    rtrt = n1;
    char arr[n][n];
    char arr_copy[n][n];
    //scanf("%d",&n1);
    int i,j;
    for(i=0;i<n1;i++){
        for(j=0;j<n1;j++){
            char ch;
            cin>>ch;
            //fflush(stdin);
            //scanf(" %c",&ch);
            arr[i][j] = ch;
            arr_copy[i][j] = ch;
        }
    }
    if(n1 == 1){
        cout<<0;
        //printf("0");
        return 0;
    }
    int ans_ = 0;
        for(i=0;i<n1;i++){
            for(j=0;j<n1;j++){
                if(arr[i][j] == '*'){
                   // flag = 1;
                    ans_ += cal_(i,j,arr_copy,n1);
                    //arr[i][j] = '-';
                    //cout<<1<<" ";
                }
            }
        }
    cout<<ans_;
    //printf("%d",ans_);
    //cal_(arr,)
    return 0;
}

我简单地应用了一个 BFS 并添加了个人 sum.The 问题是它只通过了一些测试用例，错误的答案和超过了时间限制 some.Can 一些请建议我缺少什么测试用例处理？

Answer 1

我会尝试这样的事情：

计算空单元格的连通面积并计算每个区域的单元格数
对于每个烟花单元，确定相邻区域并将它们的计数相加（烟花单元本身 +1）

代码未通过所有测试用例

Code not passing all test cases

c++

algorithm

graph

breadth-first-search