Ciao a tutti, ho bisogno di aiuto per risolvere il problema Find the Treasure.
Mi dà sbagliate le subtask 3 e 4 (N=3 o M=3) e 7, ma non mi vengono in mente casi limite in cui il programma non funziona.
Ecco il mio codice:
#include<bits/stdc++.h>
using namespace std;
#ifdef EVAL
#define debug(x) (x)
#else
#define debug(x) ( cerr << “[” << LINE << "] " << #x << " → " << (x) << endl, (x) )
#endif
bool visti[1001][1001];
short mappa[1001][1001];
int n, m;
bool visitati[1001][1001];
bool bfs(int r, int c){
if(visitati[r][c]) return false;
queue<pair<int,int>> qu;
qu.push({r,c});
while(!qu.empty()){
int x = qu.front().first, y = qu.front().second; qu.pop();
if(x==0 || x==n-1 || y==0 || y==m-1) return false;
visitati[y] = true;
int dx = {0, 0, 1, -1};
int dy = {1, -1, 0, 0};
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
if (mappa[nx][ny] == 1 && !visitati[nx][ny]) {
visitati[nx][ny] = true;
qu.push({nx, ny});
}
}
}
}
//cout << r << " " << c << endl;
return true;
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin >> n >> m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++) cin >> mappa[i][j];
}
int island = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(!visitati[i][j] && mappa[i][j] == 1 && bfs(i,j)) island++;
}
}
cout << island << endl;
return 0;
}
Grazie mille in anticipo!