TrendyTrash 58/100 Execution Timed Out

Aiuto
1

#include
#include
#include
using namespace std;

int pulisci(int N, int M, vector S)
{
bool totalMovesFinished = false;
int cancelled = 0;

int mat[N][M];
int ca = 0;
int pl = 0;
int nul = 0;
int totalCount = 0;

int r = 0;
for (auto s : S)
{
int c = 0;
for (char ch : s)
mat[r][c++] = ch - ‘0’;

r++;

}
while (!totalMovesFinished)
{
cancelled = 0;
for (int i = 0; i < N; i++)
{
ca = 0;
pl = 0;
nul = 0;

  for (int j = 0; j < M; j++)
  {
    if (mat[i][j] == 1)
    {
      ca++;
    }
    else if (mat[i][j] == 0)
    {
      pl++;
    }
    else
    {
      nul++;
    }
  }
  if ((nul != M) && (pl == M || pl + nul == M))
  {
    cancelled++;
    for (int j = 0; j < M; j++)
    {
      if (mat[i][j] != -1)
      {
        mat[i][j] = -1;
        totalCount++;
      }
    }
  }
  else if ((nul != M) && (ca == M || ca + nul == M))
  {
    cancelled++;
    for (int j = 0; j < M; j++)
    {
      if (mat[i][j] != -1)
      {
        mat[i][j] = -1;
        totalCount++;
      }
    }
  }
}

for (int j = 0; j < M; j++)
{

  ca = 0;
  pl = 0;
  nul = 0;

  for (int i = 0; i < N; i++)
  {
    if (mat[i][j] == 1)
    {
      ca++;
    }
    else if (mat[i][j] == 0)
    {
      pl++;
    }
    else
    {
      nul++;
    }
  }
  if ((nul != N) && (pl == N || pl + nul == N))
  {
    cancelled++;
    for (int i = 0; i < N; i++)
    {
      if (mat[i][j] != -1)
      {
        mat[i][j] = -1;
        totalCount++;
      }
    }
  }
  else if ((nul != N) && (ca == N || ca + nul == N))
  {
    cancelled++;
    for (int i = 0; i < N; i++)
    {
      if (mat[i][j] != -1)
      {
        mat[i][j] = -1;
        totalCount++;
      }
    }
  }
}
if(cancelled == 0){
  totalMovesFinished = true;
}

}
return (N * M) - totalCount;
}

int main()
{
int N, M;

cin >> N >> M;

vector S(N);

for (int i = 0; i < N; i++)
{
cin >> S[i];
}

cout << pulisci(N, M, S) << endl;

return 0;
}

Ho capito che il problema è greedy, ma ho inziato descrivendo questa soluzione, qualcuno che mi sa dare una dritta per ridurre l’execution time?

2

Per favore puoi formattare correttamente il codice?

2 Mi Piace