Robię to zadanie: http://www.usaco.org/index.php?page=viewproblem2&cpid=836
Moj pomysl jest taki ze tworze graf z regionów a poźniej dość brutalnie sprawdzam czy jakaś para krów może stworzyć największy region, jednak moim problemem jest coś innego a dokładnie vector<vector<int>> colors(MAXN, vector<int>(MAXN, 0))
jest to globalny wektor wektrów, program dla niektórych danych działa prawidłowo a dla innych nie, wykrzacza się tutaj
void make_conn(int i, int j, int color){
colors[i][j] = color;
for (int d = 0; d < 4; d++){
int ii = i + x[d], jj = j + y[d];
if (ii >= 0 && jj >= 0 && ii < n && jj < n){
// Tutaj segmetation Fault, dalczego?
int xd = colors[1][0];
int blad = colors[ii][jj];
if (graph_id[i][j] == graph_id[ii][jj] && colors[ii][jj] == 0)
make_conn(ii, jj, color);
else
graph[graph_id[i][j]].child.insert(graph_id[ii][jj]);
}
}
}
Błąd: Segmentation Fault, nie wiem tylko dlaczego skoro na pewno colors[1][0] istnieje
Do tego dzieje się coś magicznego
int id = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (graph_id[i][j] == 0){
if(i == 23 && j == 18)
int wtf = 23 * 18;
int cnt = 0;
dfs(i, j, ++id, board, cnt);
// w tym miejscu dzieje sie magia
graph[id].cow = board[i][j];
//w jakis sposob graph[id].cow = board[i][j] nie wplywa tylko na
//graph[id].cow ale tez na colors[0][14] nie wiem dlaczego
graph[id].amount = cnt;
same[board[i][j]].push_back(id);
max_one = max(max_one, cnt);
}
graph[id].cow = board[i][j];
ale też z jakiegoś powodu colors[0][14] też zamienia się na board[i][j], tak przynajmniej pokazuje mój debugger, debuguje w Visual Studio Code a debugger to chyba GDB
Ktoś pomoże mi zrozumieć dlaczego tak się dzieje?
Tutaj cały kod, niestety bardzo zwiły
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
void setIO(string s){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (s != ""){
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
}
class Vertex{
public:
unordered_set<int> child;
int cow;
int amount;
};
const int INF = 1e9 + 7, MAXN = 250 + 7;
vector<Vertex> graph(MAXN);
vector<vector<int>> colors(MAXN, vector<int>(MAXN, 0));
vector<vector<int>> graph_id(MAXN, vector<int>(MAXN, 0));
vector<vector<int>> same((int)1e6 + 7);
vector<int> x = {1, -1, 0, 0};
vector<int> y = {0, 0, 1, -1};
int n, max_one = 0, max_two = 0;
void dfs(int i, int j, int id, vector<vector<int>>& board, int& cnt){
graph_id[i][j] = id;
cnt++;
for (int d = 0; d < 4; d++){
int ii = i + x[d], jj = j + y[d];
if (ii >= 0 && jj >= 0 && ii < n && jj < n && board[ii][jj] == board[i][j] && graph_id[ii][jj] == 0)
dfs(ii, jj, id, board, cnt);
}
}
void make_conn(int i, int j, int color){
colors[i][j] = color;
for (int d = 0; d < 4; d++){
int ii = i + x[d], jj = j + y[d];
if (ii >= 0 && jj >= 0 && ii < n && jj < n){
// Tutaj segmetation Fault, dalczego?
int xd = colors[1][0];
int blad = colors[ii][jj];
if (graph_id[i][j] == graph_id[ii][jj] && colors[ii][jj] == 0)
make_conn(ii, jj, color);
else
graph[graph_id[i][j]].child.insert(graph_id[ii][jj]);
}
}
}
void fuzion(int f_cow, int s_cow, int v, vector<int>& seen, int color, int& cnt){
seen[v] = color;
cnt += graph[v].amount;
for (auto& child : graph[v].child)
if (seen[child] != color && (graph[child].cow == f_cow || graph[child].cow == s_cow))
fuzion(f_cow, s_cow, child, seen, color, cnt);
}
int main(){
setIO("");
cin >> n;
vector<vector<int>> board(n, vector<int>(n));
for (auto& row : board)
for (auto& num : row)
cin >> num;
int id = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (graph_id[i][j] == 0){
if(i == 23 && j == 18)
int wtf = 23 * 18;
int cnt = 0;
dfs(i, j, ++id, board, cnt);
// w tym miejscu dzieje sie magia
graph[id].cow = board[i][j];
//w jakis sposob graph[id].cow = board[i][j] nie wplywa tylko na
//graph[id].cow ale tez na colors[0][14] nie wiem dlaczego
graph[id].amount = cnt;
same[board[i][j]].push_back(id);
max_one = max(max_one, cnt);
}
int color = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (colors[i][j] == 0)
make_conn(i, j, ++color);
color = 1;
vector<int> seen(id+1);
for (int i = 1; i <= (int)1e6 ; i++){
unordered_set<int> to_visit;
for (auto& v : same[i])
for (auto& child : graph[v].child)
if (graph[child].cow != i)
to_visit.insert(graph[child].cow);
for (auto& s : to_visit)
for (auto& id_graph : same[i])
if (seen[id_graph] != color){
int cnt = 0;
fuzion(i, s, id_graph, seen, ++color, cnt);
max_two = max(max_two, cnt);
}
}
cout << max_one << "\n" << max_two << "\n";
return 0;
}
/*
10
*/
Test który powoduje Segmentation fault i inne magiczne błędy
https://pastebin.com/nDvUnvug