Testing NZEC

It certainly is.

As long as you understand what a NZEC is, you've been given all of the tools in the problem statement to find it.

Using the constraints of the problem statement you should be able to see likely places where array bounds might be exceeded, or memory limits might be tested for stack overflow.

Compile time is not where an NZEC occurs.

The way to test it is with test cases that stress the limits of the problem constraints.

Pardon me, I thought you were running the contest and knew how to execute a c program already.

I'm in a windows environment.
I create a file called test.c that has my c code.

I compile the code using:
gcc test.c test.exe

I create a file called test.in that has the input I want to test in it.

I execute the code using:
test.exe test.out

The output of my program will be in test.out

A NZEC is caused at runtime due to an application aborting for some reason other than 0 (success)

There are a plethora of reasons, the most common of which (in the spoj area) are reading outside of array bounds or stack overflow.

There is no way to "test" these without actually causing them. Usually when they occur for me, it's due to not evaluating the constraints properly.

Tak, teraz wejście jest ok.
Jeżeli jesteś początkujący[m] to powinieneś zaczynać od łatwiejszych rzeczy, od czytania opisów i pseudokodów [łatwiejszych] algorytmów, a nie od kopiowania gotowych. Data, na stronie RN z algorytm dijkstry, to 2007 rok. Od tego czasu, mogło się trochę pozmieniać, zarówno sam kompilator jak i STL.
Powinieneś poszukać i poczytać o tym algorytmie [dijkstry] w innych źródłach.

.
PS
Wydaje mi się, że ta instrukcja powoduje problem [zawieszenie-zapętlenie], gdy w kopcu [set] nie ma v
[bbone=cpp,2186] kopiec.erase(kopiec.find(v)); [/bbone]
wystarczy poprzedzić ją warunkiem sprawdzającym:
[bbone=cpp,2187]if(kopiec.find(v) != kopiec.end())
kopiec.erase(kopiec.find(v)); [/bbone]
lub, aby dwukrotnie nie uruchamiać find() :
[bbone=cpp,2188] set::iterator it;
if((it = kopiec.find(v)) != kopiec.end())
kopiec.erase(it);[/bbone]

Tak i jeżeli chcemy go [algorytm] użyć dla grafu nieskierowanego, to czy nie wystarczy dodać?:
[bbone=cpp,2190] adj[a].push_back( pair(b,c) );
adj[b].push_back( pair(a,c) ); [/bbone]

Wystarczy Napisałem tylko, żeby lukib zwrócił uwagę jeśli dalej będzie testował i coś mu nie będzie wychodziło. Faktycznie mogłem dopisać jak Ty co należy dodać by działał i dla nieskierowanych.

Bardzo zacna i fajna strona i twój post też jest fajny, zacny i kolorowy . Dzięki!

Wydaje mi się, że chcąc maksymalnie zoptymalizować, za bardzo komplikujesz i sam kod i podejście do zadania.
Na "twojej" stronie: redblobgames.com/pathfinding ... ction.html

I właśnie tutaj wydaje mi się, że algorytm fllod fill, bez optymalizacji [A*, Dijkstra itd], jest już wystarczający do rozwiązania tego zadania. Problemem jest tylko wymyślenie sposobu, jak go tu zastosować.

W kategorii średnich, są dwa łatwiejsze zadania [i dyskusje z nimi związane, na forum]:
12985. Hodowla reniferów, 14403. Linia brzegowa, które można i warto zrobić na rozgrzewkę, jeżeli jeszcze ich nie robiłeś

to zadanie naprawdę nie jest zbyt trudne, raczej powinno by w średnich

zamieszczony test bardzo ładny, ale przydatny tylko do sprawdzenia czasu - brak podziału na rozłączne akweny, brak labiryntów, wysp w kształcie grzebieni

wynik do tego testu zamieszczam poniżej, mam nadzieję, że nie pomyliłem się przy przepisywaniu

[bbone=text,2197]2 2 2 2 3 3 3 3 4 4 5 5 5 5 5 6 6 6 6 6 6 7 8 8 8 9 9 9 9 9 9 9 10 10 11 11 11 11 11 12 12 12 13 13 13 13 13 13 14 14 15 15 15 15 16 17 17 17 17 17 17 17 17 18 18 18 18 19 19 19 19 19 20 20 20 20 20 20 21 21 21 21 21 21 21 22 22 22 22 22 22 23 23 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 27 27 27 27 27 27 28 28 28 29 29 29 29 30 30 30 31 31 31 31 32 32 32 32 32 33 33 33 33 33 33 33 33 34 34 34 34 34 35 35 35 35 35 35 36 36 36 37 37 37 37 37 37 37 37 38 38 38 38 38 38 38 38 38 38 38 38 39 39 39 39 39 39 39 39 39 39 39 40 40 40 40 40 40 40 40 41 41 41 41 41 41 41 41 42 42 42 42 42 42 42 42 43 43 43 43 43 43 43 43 43 43 44 44 44 44 44 44 44 44 44 45 45 45 45 46 46 46 46 46 46 46 46 46 46 47 47 47 47 47 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 49 49 49 49 49 49 49 49 50 50 50 50 50 50 50 50 50 51 51 51 51 51 52 52 52 52 53 53 53 53 53 53 53 54 54 54 54 54 54 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 56 56 56 56 56 56 57 57 57 57 57 57 57 57 57 57 57 57 57 57 57 58 58 58 58 58 58 58 58 58 58 58 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 59 60 60 60 60 60 60 60 60 61 61 61 61 61 62 62 62 62 62 62 62 62 62 62 62 62 63 63 63 63 63 63 63 63 63 63 63 63 63 64 64 64 64 64 64 65 65 65 65 65 65 65 65 65 65 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 68 68 68 68 68 68 68 68 68 69 69 69 69 69 69 69 70 70 70 70 70 70 70 71 71 71 71 71 71 71 71 71 71 72 72 72 72 72 72 72 73 73 73 73 73 73 73 73 73 73 73 73 73 73 73 74 74 74 74 74 74 74 74 74 74 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 75 76 76 76 76 76 76 76 76 77 77 77 77 77 77 77 77 77 77 77 77 77 77 78 78 78 78 78 78 78 78 78 78 78 78 78 79 79 79 79 79 79 79 79 79 79 80 80 80 80 80 80 80 80 81 81 81 81 81 81 81 81 81 82 82 82 82 82 82 82 82 82 82 82 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 84 84 84 84 84 84 84 84 84 84 84 84 84 85 85 85 85 85 85 85 85 85 85 85 86 86 86 86 86 86 87 87 87 87 87 87 87 87 87 87 87 87 87 87 88 88 88 88 88 88 88 88 89 89 89 89 89 89 89 89 89 89 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 91 91 91 91 91 91 91 91 91 91 91 92 92 92 92 92 92 92 92 92 92 92 92 92 92 93 93 93 93 93 93 93 93 93 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 94 95 95 95 95 95 95 95 95 95 95 95 95 95 95 95 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 97 97 97 97 97 97 97 97 97 97 97 97 97 98 98 98 98 98 98 98 98 98 99 99 99 99 99 99 99 99 99 99 99 99 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 102 102 102 102 102 102 102 102 102 102 102 102 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 103 104 104 104 104 104 104 104 104 104 104 104 105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 105 106 106 106 106 106 106 106 106 106 106 106 106 106 106 106 106 106 106 106 107 107 107 107 107 107 107 107 107 107 107 107 108 108 108 108 108 108 108 108 108 108 108 108 108 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 109 110 110 110 110 110 110 110 110 110 110 110 110 111 111 111 111 111 111 111 111 111 111 111 112 112 112 112 112 112 112 112 112 112 112 112 112 112 112 112 112 112 112 112 113 113 113 113 113 113 113 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 114 115 115 115 115 115 115 115 115 115 115 115 115 115 115 115 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 116 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 117 118 118 118 118 118 118 118 118 118 118 118 118 118 118 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 119 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 120 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 122 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 123 124 124 124 124 124 124 124 124 124 124 124 124 125 125 125 125 125 125 125 125 125 125 125 125 125 125 125 126 126 126 126 126 126 126 126 126 126 126 126 126 126 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 127 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 130 130 130 130 130 130 131 131 131 131 131 131 131 131 131 131 131 131 131 131 131 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 132 133 133 133 133 133 133 133 133 133 133 133 133 133 133 133 134 134 134 134 134 134 134 134 134 134 134 134 134 134 134 134 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 135 136 136 136 136 136 136 136 136 136 136 136 136 136 136 137 137 137 137 137 137 137 137 137 137 137 137 137 137 138 138 138 138 138 138 138 138 138 138 138 139 139 139 139 139 139 139 139 139 139 139 139 139 139 140 140 140 140 140 140 140 140 140 140 140 140 140 140 140 140 141 141 141 141 141 141 141 141 141 141 141 141 141 142 142 142 142 142 142 142 142 142 142 142 142 142 142 142 142 143 143 143 143 143 143 143 143 143 143 143 143 143 143 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 145 146 146 146 146 146 146 146 146 146 146 146 146 146 146 147 147 147 147 147 147 147 147 147 147 147 147 147 147 148 148 148 148 148 148 148 148 148 148 148 148 148 148 148 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 149 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 151 151 151 151 151 151 151 151 151 151 151 151 151 151 151 151 151 151 151 152 152 152 152 152 152 152 152 152 152 152 152 152 152 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 153 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 154 155 155 155 155 155 155 155 155 155 155 155 155 155 156 156 156 156 156 156 156 156 156 156 156 156 156 156 156 156 156 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 157 158 158 158 158 158 158 158 158 158 158 158 158 159 159 159 159 159 159 159 159 159 159 159 159 159 159 159 160 160 160 160 160 160 160 160 160 160 160 160 160 160 161 161 161 161 161 161 161 161 161 161 161 161 161 161 161 162 162 162 162 162 162 162 162 162 162 162 163 163 163 163 163 163 163 163 163 163 163 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 165 166 166 166 166 166 166 166 166 166 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 168 168 168 168 168 168 168 168 168 168 168 168 168 169 169 169 169 169 169 169 169 169 169 169 169 169 169 170 170 170 170 170 170 170 170 170 170 170 170 170 170 170 170 170 170 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 171 172 172 172 172 172 172 172 172 172 172 172 172 172 173 173 173 173 173 173 173 173 173 173 173 173 173 173 174 174 174 174 174 174 174 174 174 174 174 174 174 174 175 175 175 175 175 175 175 175 175 175 176 176 176 176 176 176 176 176 176 176 176 176 176 176 177 177 177 177 177 177 177 177 177 177 177 177 177 177 177 178 178 178 178 178 178 178 178 178 178 178 178 178 178 179 179 179 179 179 179 179 179 179 179 179 179 179 179 179 179 179 179 179 179 179 180 180 180 180 180 180 180 180 180 180 180 180 181 181 181 181 181 181 181 181 181 181 181 182 182 182 182 182 182 182 182 182 182 182 182 182 182 182 182 182 182 182 182 183 183 183 183 183 183 183 183 183 183 183 184 184 184 184 184 184 184 184 184 184 184 185 185 185 185 185 185 185 185 185 185 185 185 185 185 185 185 185 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 186 187 187 187 187 187 187 187 187 187 187 187 188 188 188 188 188 188 188 188 188 188 189 189 189 189 189 189 189 189 189 189 189 189 189 189 189 189 189 189 189 190 190 190 190 190 190 190 190 190 190 190 190 190 190 190 190 190 190 190 191 191 191 191 191 191 191 191 191 191 191 191 191 191 191 191 191 191 191 192 192 192 192 192 192 192 192 192 192 192 192 192 192 192 193 193 193 193 193 193 193 193 193 193 193 193 193 193 193 193 194 194 194 194 194 194 194 194 194 194 194 194 194 194 194 195 195 195 195 195 195 195 195 195 195 196 196 196 196 196 196 196 196 196 196 196 196 196 197 197 197 197 197 197 197 197 197 197 197 197 197 197 197 197 198 198 198 198 198 198 198 198 198 198 198 198 198 198 198 198 198 198 199 199 199 199 199 199 199 199 199 199 199 199 199 199 199 199 199 200 200 200 200 200 200 200 200 200 201 201 201 201 201 201 201 201 201 201 202 202 202 202 202 202 202 202 202 202 202 202 202 202 202 202 203 203 203 203 203 203 203 203 203 203 203 203 203 203 203 203 203 203 204 204 204 204 204 204 204 204 204 204 204 204 204 205 205 205 205 205 205 205 205 205 205 205 205 205 205 205 206 206 206 206 206 206 206 206 206 206 206 206 206 206 206 207 207 207 207 207 207 207 207 208 208 208 208 208 208 208 208 208 208 209 209 209 209 209 209 209 209 209 209 209 210 210 210 210 210 210 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 211 212 212 212 212 212 212 212 212 212 212 212 212 212 212 213 213 213 213 213 213 213 213 213 213 213 213 213 213 213 213 214 214 214 214 214 214 214 214 214 214 214 214 214 215 215 215 215 215 215 215 215 215 215 215 215 215 215 215 215 215 215 215 215 215 216 216 216 216 216 216 217 217 217 217 217 217 217 217 217 217 217 217 218 218 218 218 218 218 218 218 218 218 218 218 219 219 219 219 219 219 219 219 219 219 219 219 219 219 219 219 219 219 220 220 220 220 220 220 220 220 220 220 221 221 221 221 221 221 221 221 221 221 221 221 221 222 222 222 222 222 222 222 222 222 222 222 222 222 222 223 223 223 223 223 223 223 223 223 223 223 223 223 223 224 224 224 224 224 224 224 224 224 224 224 225 225 225 225 225 225 225 225 226 226 226 226 226 226 226 226 226 227 227 227 227 227 227 227 227 227 227 227 227 227 228 228 228 228 228 228 228 228 228 228 229 229 229 229 229 229 229 229 229 229 229 229 229 229 230 230 230 230 230 230 230 230 230 231 231 231 231 231 231 231 231 231 231 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 232 233 233 233 233 233 233 233 233 233 233 234 234 234 234 234 234 234 234 234 234 234 234 235 235 235 235 235 235 235 235 235 235 235 235 235 235 235 235 235 235 235 235 235 236 236 236 236 236 236 236 236 236 237 237 237 237 237 237 237 237 237 237 237 237 237 237 238 238 238 238 238 238 238 238 238 238 238 239 239 239 239 239 239 239 239 239 239 239 239 240 240 240 240 240 240 240 240 240 240 240 240 240 241 241 241 241 241 241 241 241 241 241 241 242 242 242 242 243 243 243 243 243 243 243 243 243 243 243 244 244 244 244 244 244 244 244 244 244 244 244 244 244 244 245 245 245 245 245 245 245 245 245 245 246 246 246 246 246 246 246 246 247 247 247 247 247 247 247 247 247 247 247 247 248 248 248 248 248 248 248 248 248 249 249 249 249 249 249 249 249 249 249 249 249 249 250 250 250 250 250 250 250 250 250 250 250 250 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 251 252 252 252 252 252 252 252 252 252 252 252 252 252 252 253 253 253 253 253 253 253 253 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 254 255 255 255 255 255 255 255 255 255 255 255 255 255 256 256 256 256 256 256 256 256 257 257 257 257 257 257 257 257 257 257 257 257 257 257 258 258 258 258 258 258 258 258 258 258 258 259 259 259 259 259 259 259 259 259 260 260 260 260 260 260 260 260 260 261 261 261 261 261 261 262 262 262 262 262 262 262 263 263 263 263 263 263 263 263 263 264 264 264 264 264 264 264 264 264 264 264 265 265 265 265 266 266 266 266 266 266 266 266 267 267 267 267 267 267 267 268 268 268 268 268 268 268 268 268 268 268 269 269 269 269 269 269 269 269 269 269 270 270 270 270 270 270 270 270 270 270 271 271 271 271 271 271 272 272 272 272 272 272 272 272 272 273 273 273 273 273 274 274 274 274 274 274 274 274 274 275 275 275 275 275 275 275 275 275 275 275 275 276 276 276 276 276 276 276 276 276 276 277 277 277 277 277 277 277 277 277 278 278 278 278 278 278 278 278 279 279 279 279 279 279 279 279 279 279 279 280 280 280 280 280 280 281 281 281 281 281 281 281 281 282 282 282 282 282 282 282 282 283 283 283 283 283 283 283 283 283 283 284 284 284 284 284 284 284 284 284 284 284 284 285 285 285 285 285 286 286 286 286 286 287 287 287 287 287 287 288 288 288 288 288 288 288 288 288 289 289 289 289 289 289 289 289 290 290 290 290 290 290 290 290 290 290 290 290 290 291 291 291 291 291 291 291 291 292 292 292 292 292 292 292 292 292 293 293 293 293 294 294 294 294 294 294 294 295 295 295 295 295 296 296 296 296 296 296 296 296 296 296 297 297 297 297 297 297 297 297 297 298 298 298 298 298 298 298 298 299 299 299 299 299 299 299 299 300 300 300 300 300 300 300 301 301 301 301 301 301 301 301 301 302 302 302 302 302 302 302 302 303 303 303 303 303 303 303 303 303 303 304 304 304 304 304 304 305 305 305 306 306 306 306 306 306 306 306 307 307 307 307 307 308 308 309 309 309 309 309 309 309 309 309 309 310 310 310 310 310 310 311 311 311 311 312 312 312 312 312 312 313 313 313 313 313 313 313 314 314 314 314 314 314 314 314 315 315 315 315 316 316 316 316 316 316 317 317 317 318 318 318 318 318 318 318 318 318 318 319 319 319 319 319 320 320 320 320 321 321 321 321 321 322 322 322 322 323 323 323 323 323 323 324 324 325 325 325 325 325 325 326 326 326 326 326 326 326 326 326 327 327 327 327 327 327 327 327 328 328 328 328 328 328 329 329 329 329 329 329 330 330 330 330 330 330 330 330 330 331 331 331 331 331 331 331 331 332 332 332 332 332 332 333 333 334 334 334 334 335 335 335 335 336 336 336 336 337 337 337 337 338 338 338 338 338 338 339 339 339 339 339 340 340 340 340 341 341 341 341 341 342 342 342 343 343 343 343 344 344 344 345 345 345 346 347 347 347 347 347 347 347 348 348 349 349 349 349 349 349 350 350 350 350 350 350 351 351 351 351 351 352 352 352 352 352 352 352 353 354 354 354 355 355 355 355 356 356 356 357 357 357 358 358 358 359 359 359 359 360 360 360 360 361 361 361 361 361 361 361 361 362 362 362 363 363 364 365 366 366 366 366 367 368 368 369 369 369 370 370 371 372 372 373 373 373 374 374 374 376 376 376 376 377 377 378 378 378 379 380 381 381 381 382 382 382 382 382 382 383 383 384 384 385 385 385 385 386 386 386 386 387 387 387 387 389 389 391 393 393 393 395 395 395 396 397 397 398 398 398 398 398 398 398 398 399 399 399 400 401 401 401 402 402 402 403 403 404 405 405 406 406 407 407 407 409 411 411 412 414 415 415 416 416 417 417 417 418 418 419 419 420 420 420 421 421 421 423 423 424 424 424 426 427 429 431 431 433 433 434 434 436 436 437 437 438 438 439 440 441 442 444 446 446 448 450 453 453 453 453 455 455 456 456 456 458 458 458 467 469 469 473 478 478 481 484 485 488 489 489 493 513 524 [/bbone]

-- Cz sty 08, 2015 3:47 pm --

mam jeszcze wątpliwość co do rozpatrywania akwenu z wyciętymi prostokątami, jest to niezgodne z moją intuicją - chyba, że istnieją jakieś dodatkowe warunki

zresztą na drugim ślicznym rysunku mamy dziwną numerację - w kolumnie na prawo od '0' mamy w pewnym miejscu '10' a po przerwie '13' - jak najbardziej prawidłowo - tylko dlaczego, jeżeli ta przerwa występuje ?

Flood-fill o którym mówisz jest powszechnie znany jako Breath First Search. Pomyślałem o tym, ale łatwo wymyśleć przykład gdzie BFS będzie niemiłosiernie wolny w porównaniu do A*, gdy prawie cała mapa to ocean. Co więcej, redukcja symetrii nie jest kompatybilna z BFS, wagi krawędzi nie są wszystkie równe 1 po redukcji. Spójrz na obrazek, wiele więcej wierzchołków zostaje odwiedzonych.

PS. Test na mniejszej mapie 300x150, 94 wyspy: sumarycznie A* odwiedził 1.2mln wierzchołków, Dijkstra 1.5mln, BFS... 34mln. Tak, po trójce nie ma kropki.

4g0Ggcp.png1426x714 123 KB

Chętnie spróbuję!

Dziękuję! Twoje wyniki zgadzają się z moimi.

Na stronie jest wyjaśnione na czym to polega. harablog.wordpress.com/2011/09/ ... reduction/
Wierzchołki wewnątrz prostokąta zostają usunięte a wierzchołki na obrzeżu zostają połączone z wierzchołkami po drugiej stronie prostokąta (wagi są długością skoku, nie 1). Pomiędzy dowolnymi wierzchołkami na obrzeżu można się przemieszczać bez użycia tych wewnątrz, z zachowaniem kosztów dojścia.

rsr_macroedges.png1089x492 57.9 KB

teraz rozumiem na czym to polega , ale nie mam zamiaru sam tego sprawdzać - dużo bardziej skomplikowany algorytm, a czas, który osiągnąłem całkiem przyzwoity

ciekawe jaki czas ty osiągniesz, gdy napiszesz to w C/C++

Tak na początek, do adminów i do moderatorów w celu wyważenia całkowicie subiektywnych opinii. To zadanie naprawdę nie jest aż takie łatwe i naprawdę powinno nadal pozostać w trudnych. Na spoju pojawiają się ciągle nowi użytkownicy i dla nich naprawdę jest i długo będzie to trudne [bardzo] zadanie.

Czemu twierdzisz, że powszechnie, skoro nawet na "twojej" stronie ujmują to trochę inaczej. Skoro jednak tak twierdzisz, nie upieram się. Dla mnie BFS to grafy, flood-fill dotyczy "mapy", którą oczywiście można też potraktować jako graf, ale .... Flood-fill może być robiony na bazie stosu, kolejki, rekurencyjnie itd i może dlatego "wygląda" trochę podobnie do BFS czy innych algorytmów grafowych, ale jednak nie dotyczy on grafów.
Wyszukiwanie pustych miejsc na oceanie i zamiana na prostokątne obszary też kosztuje - a jeżeli takie miejsca są to automatycznie mniej jest też wysp i mniej też wykonamy floodów więc czy tak naprawdę skórka warta wyprawki?

Tak bardzo, bardzo z grubsza szacując flood-fill to: 300 x 150 x 93 = 4 185 000 odwiedzonych "kratek", więc można spokojnie skorzystać właśnie z fill-floda, a dopiero potem, ewentualnie bawić się w optymalizacje.
Lepiej mieć wolniejsze ale działające [AC lub nawet TLE] rozwiązanie, niż super inteligentne i z najlepszymi optymalizacjami ale bez akceptacji [WA]. Posiadając taki wolniejszy program, możemy nim sprawdzać swoje testy, chociaż w takich wypadkach najlepszym sprawdzaniem jest zawsze AC na Spoju - przeważnie nie wiemy jakich testów możemy się spodziewać. CHyba, że masz awersję do dużej ilości zgłoszeń WA i TLE - zobacz: spoj.com/MBCONT00/problems/MBPROB01/
Do wcześniejszej listy zadań można dodać: 22159. Stawy i grobla, ze średnich oraz możliwe, że znalazłoby się parę w wyższych kategoriach.

Przepisałem kod do C. Czas dla gistfile1 wynosi ~17 sek. Gdyby ktoś chciał mi wytknąć co można usprawnić byłbym wdzięczny. Z góry przepraszam za brak objaśnień w kodzie. Gist prezentuje kod ładniej niż code tag więc tam wkleiłem kod. gist.github.com/anonymous/842f7e36dd3dc95774e4

Narbej, odpowiem na twój post później.

Uprościłem kod. Zszedłem z 17 sek do 10 sek w teście. Nadal daleko do zera...
gist.github.com/anonymous/0dc5fb94c02c10867a0a1

Ciężko mi to rozwinąć, bo powinienem w końcu zrobić to zadanie, a dopiero wtedy się wypowiadać i doradzać. Chodził mi o to, że "dobierając" się do rozwiązywania jakiegoś zadania trzeba dobrze przemyśleć strategię. Nieraz trzeba podejść jak

czy z młotkiem i zapomnieć o super optymalizacjach i udziwnieniach. Nie mówię, że twój sposób jest zły - po prostu nie wiem, ale jak dla mnie, za dużo tablic i kodu
Jeżeli chodzi o to moje mini zadanie, to należało by się jeszcze zorientować jak wielka jest macierz, czy szukana wartość wystąpi i czy tylko raz, czy może tylko na dolnej lub górnej krawędzi, czy wystąpi murek, a może ta szukana wartość wystąpi także na środku macierzy itd. A może macierz jest typu 1xm lub mx1. Kiedyś może próbowałbym może tak kombinować, ale teraz po prostu "przeleciałbym" po całej macierzy. Więcej nawet zrezygnowałbym z indeksów na rzecz wskaźnika *ip:
[bbone=cpp,2239]
macierz[M][N];
ip = macierz;
while (*ip != szukana) ++ip;
[/bbone]proste jak młotek, czy tępa siekiera , chociaż jest tu mały haczyk - ale nie będę rozwijał - jak ktoś ma wątpliwości to pytać. Szukany może być też zakres lub kilka a nie jedna konkretna wartość.

Jeżeli chodzi o flood-fill to .... może następnym razem

Obrazki śliczne, i w końcu domyśliłeś się, że można startować jednocześnie z całego brzegu wyspy

i teraz to zadanie naprawdę stało się łatwe - bo nawet bez zamieszczonej jednej linijki kodu, dzięki tym obrazkom widać rozwiązanie