Program robi coś innego niż mu każe, magia C++ proszę o pomoc

0

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

2

Czy słyszałeś o czymś takim jak debugger?

0

Z tego co wiem to C++ obsługuję wyjątki - blok try catch. W bloku catch pewnie można wyświetlić informację, w którym to miejscu wychodzisz po za zakres przydzielonej pamięci.

0

Na codzień nie piszę w C++ ale znalazłem informacje że do lokalizacji tego typu błędu możesz użyć kompilator g++ (z flagą kompilacji -g) oraz debuger gdb. Radzę ci jednak abyś postarał się lepiej zrozumieć swój kod.

0

Odpalisz to pod debugerem to się dowiesz, które miejsce powoduje segfaulta. Żadnej magii tu nie podejrzewam.

4

Naucz się korzystać z narzędzi, polecam address sanitizer:

Mac-mini:4progCows$ vi main.cpp && g++ -std=c++17 -O3 -g -fsanitize=address main.cpp -o cows
Mac-mini:4progCows$ ./cows data
=================================================================
==53864==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x627000003158 at pc 0x0001073bf17c bp 0x7ffee88477d0 sp 0x7ffee88477c8
WRITE of size 4 at 0x627000003158 thread T0
    #0 0x1073bf17b in main main.cpp:86
    #1 0x7fff20652620 in start+0x0 (libdyld.dylib:x86_64+0x15620)

0x627000003158 is located 40 bytes to the right of 12336-byte region [0x627000000100,0x627000003130)
allocated by thread T0 here:
    #0 0x10797b7ed in wrap__Znwm+0x7d (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x557ed)
    #1 0x1073bb505 in std::__1::vector<Vertex, std::__1::allocator<Vertex> >::vector(unsigned long) vector:1119
    #2 0x1073c289c in _GLOBAL__sub_I_main.cpp main.cpp
    #3 0x10782b078 in ImageLoaderMachO::doModInitFunctions(ImageLoader::LinkContext const&)+0x22e (dyld:x86_64+0x1d078)
    #4 0x10782b477 in ImageLoaderMachO::doInitialization(ImageLoader::LinkContext const&)+0x27 (dyld:x86_64+0x1d477)
    #5 0x107825d19 in ImageLoader::recursiveInitialization(ImageLoader::LinkContext const&, unsigned int, char const*, ImageLoader::InitializerTimingList&, ImageLoader::UninitedUpwards&)+0x1eb (dyld:x86_64+0x17d19)
    #6 0x107823b81 in ImageLoader::processInitializers(ImageLoader::LinkContext const&, unsigned int, ImageLoader::InitializerTimingList&, ImageLoader::UninitedUpwards&)+0xbb (dyld:x86_64+0x15b81)
    #7 0x107823c21 in ImageLoader::runInitializers(ImageLoader::LinkContext const&, ImageLoader::InitializerTimingList&)+0x51 (dyld:x86_64+0x15c21)
    #8 0x10781062e in dyld::initializeMainExecutable()+0xc6 (dyld:x86_64+0x262e)
    #9 0x1078169a3 in dyld::_main(macho_header const*, unsigned long, int, char const**, char const**, char const**, unsigned long*)+0x205f (dyld:x86_64+0x89a3)
    #10 0x10780f22a in dyldbootstrap::start(dyld3::MachOLoaded const*, int, char const**, dyld3::MachOLoaded const*, unsigned long*)+0x1c8 (dyld:x86_64+0x122a)
    #11 0x10780f024 in _dyld_start+0x24 (dyld:x86_64+0x1024)

SUMMARY: AddressSanitizer: heap-buffer-overflow main.cpp:86 in main
Shadow bytes around the buggy address:
  0x1c4e000005d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1c4e000005e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1c4e000005f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1c4e00000600: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1c4e00000610: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x1c4e00000620: 00 00 00 00 00 00 fa fa fa fa fa[fa]fa fa fa fa
  0x1c4e00000630: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c4e00000640: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c4e00000650: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c4e00000660: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c4e00000670: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==53864==ABORTING
Abort trap: 6

A problem polega na tym, że zwiększasz zmienną id poza rozmiar graph.

0

Valgind też jest dobrym narzędziem:

(base) bartek@telegonos:~/cows$ valgrind ./a.out < data 
==20127== Memcheck, a memory error detector
==20127== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==20127== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==20127== Command: ./a.out
==20127== 
==20127== Invalid write of size 4
==20127==    at 0x10AE76: main (moo.cpp:86)
==20127==  Address 0x4ddfcf8 is 8 bytes before a block of size 1,028 free'd
==20127==    at 0x483CFBF: operator delete(void*) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==20127==    by 0x10E9BD: __gnu_cxx::new_allocator<int>::deallocate(int*, unsigned long) (new_allocator.h:128)
==20127==    by 0x10E04E: std::allocator_traits<std::allocator<int> >::deallocate(std::allocator<int>&, int*, unsigned long) (alloc_traits.h:470)
==20127==    by 0x10D673: std::_Vector_base<int, std::allocator<int> >::_M_deallocate(int*, unsigned long) (stl_vector.h:351)
==20127==    by 0x10C917: std::_Vector_base<int, std::allocator<int> >::~_Vector_base() (stl_vector.h:332)
==20127==    by 0x10BE4E: std::vector<int, std::allocator<int> >::~vector() (stl_vector.h:680)
==20127==    by 0x10B60B: __static_initialization_and_destruction_0(int, int) (moo.cpp:27)
==20127==    by 0x10B94B: _GLOBAL__sub_I__Z5setIONSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE (moo.cpp:122)
==20127==    by 0x11074C: __libc_csu_init (in /home/bartek/cows/a.out)
==20127==    by 0x4AAB03F: (below main) (libc-start.c:264)
==20127==  Block was alloc'd at
==20127==    at 0x483BE63: operator new(unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==20127==    by 0x10EB85: __gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*) (new_allocator.h:114)
==20127==    by 0x10E220: std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) (alloc_traits.h:444)
==20127==    by 0x10D93B: std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) (stl_vector.h:343)
==20127==    by 0x10D60A: std::_Vector_base<int, std::allocator<int> >::_M_create_storage(unsigned long) (stl_vector.h:358)
==20127==    by 0x10C8AE: std::_Vector_base<int, std::allocator<int> >::_Vector_base(unsigned long, std::allocator<int> const&) (stl_vector.h:302)
==20127==    by 0x10BDCA: std::vector<int, std::allocator<int> >::vector(unsigned long, int const&, std::allocator<int> const&) (stl_vector.h:521)
==20127==    by 0x10B5E0: __static_initialization_and_destruction_0(int, int) (moo.cpp:27)
==20127==    by 0x10B94B: _GLOBAL__sub_I__Z5setIONSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE (moo.cpp:122)
==20127==    by 0x11074C: __libc_csu_init (in /home/bartek/cows/a.out)
==20127==    by 0x4AAB03F: (below main) (libc-start.c:264)
...

Masz od razu podpowiedź, że chodzi o operację zapisu a nie odczytu (czyli problemem jest raczej graph[id].cow a nie board[i][j]

1

Nie ogarniam twojego kodu i tego nie planuje.

Moja rada zainteresuj się pisaniem testów.
Zacznij od poprawiania funkcji scoreCowGame tak by przechodziła proste testy: https://godbolt.org/z/Mchbsf1Kr

0

Przed uruchamianiem warto też dać ulimit -c unlimited, żeby core dumpy się pojawiały.

Wiesz, w którym miejscu wywala, ale błąd jest wcześniej. Jak w gdb dasz print colors[1].size() do wychodzi bardzo duża liczba, więc coś z inicjalizacją drugiego wiersza nie wyszło

0
_13th_Dragon napisał(a):

Czy słyszałeś o czymś takim jak debugger?

Tak, przecież napisałem że debugger pokazuje Segmentatnion fault w tym miejscu:

            int xd = colors[1][0];
            int blad = colors[ii][jj];
            if (graph_id[i][j] == graph_id[ii][jj] && colors[ii][jj] == 0)
MarekR22 napisał(a):

A problem polega na tym, że zwiększasz zmienną id poza rozmiar graph.

Bardzo dziękuje po poprawieniu na MAXN * MAXN kod przechodzi wszystkie testy na USACO :D
@MarekR22 Skąd wiadomo z tego narzędzia że to rozmiar graph był problemem?

Zastanawia mnie tylko dlaczego debugger nie pokazał mi błędu tutaj:

                graph[id].cow = board[i][j];
                graph[id].amount = cnt;

przecież id wtedy wychodzi poza rozmiar graph, dlaczego debugger tego nie sygnalizuje?

2

@MarekR22 Skąd wiadomo z tego narzędzia że to rozmiar graph był problemem?

Zastanawia mnie tylko dlaczego debugger nie pokazał mi błędu tutaj:

                graph[id].cow = board[i][j];
                graph[id].amount = cnt;

przecież id wtedy wychodzi poza rozmiar graph, dlaczego debugger tego nie sygnalizuje?

==53864==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x627000003158 at pc 0x0001073bf17c bp 0x7ffee88477d0 sp 0x7ffee88477c8
WRITE of size 4 at 0x627000003158 thread T0
    #0 0x1073bf17b in main main.cpp:86

Błąd by podczas zapisywania danych w linii:

graph[id].cow = board[i][j];

Czyli graph[id].cow musu być nieprawidłowe. Standardowy błąd to za duża wartość id, wiec wystarczy to zweryfikować (co zrobiłem).

Address sanitizer ma tą przewagę nad zwykłym debugowaniem, że łapie w zasadzie wszystkie błędy pamięci.
Jako, ze jest to "undefined Behavior" to crash nie jest gwarantowany, więc błędy pamięci czasami nie wychodzą or razu (raz mi się zdarzyło podczas rekrutacji i straciłem sporo czas na szukanie błędu, bo nie było crasha tylko zły wynik obliczeń).
Na dodatek, Address Sanitizer daje więcej informacji technicznych (np jaki kod zwolnił dany blok pamięci).

Polecam uczyć się pisania testów. To jest ważniejsza umiejętność niż rozwiązywania takich zadań. Jeśli planujesz karierę programisty to jest konieczna umiejętność.
Pisanie testów jest proste, próg wejścia jest dość niski, a ich poziom zaawansowania można stopniowo zwiększać.
Obecnie wiodące biblioteki to catch2 (to co użyłem w przykładzie, dość nowe ale nabiera rozpędu) i gtest (w zasadzie standardowe rozwiązanie dla C++).

1

Tak, a propos zacznij używać kontenerów standardowych, wtedy błędów będzie mniej zaś kod będzie jakieś dwa razy krótszy.

1
Suchy702 napisał(a):
                graph[id].cow = board[i][j];
                graph[id].amount = cnt;

przecież id wtedy wychodzi poza rozmiar graph, dlaczego debugger tego nie sygnalizuje?

Mógłbyś to wykryć bez debugera:

                graph.at(id).cow = board[i][j];

.at() w przeciwieństwie [] rzuca wyjątek gdy adres zostanie przekroczony.

Żeby gdb sygnalizował przekroczenie pewnej wartości stwórz breakpoint z warunkiem w podejrzanych miejscach:

(gdb) break cow.cpp:95 if id > 249

Zamiast podawać numer linii (np. 95) możesz zastosować etykiety:

loop1:
                ...
                graph[id].cow = board[i][j];

(gdb) break cow.cpp:loop1 if id > 249

1 użytkowników online, w tym zalogowanych: 0, gości: 1