SPOJ: BITMAP

1
3 4
0001
0011
0110
3 2 1 0
2 1 0 0
1 0 0 1

Brute Force Approach:

  1. The 2-D array is a[m][n], say.
  2. Store the co-ordinates of all the 1's in a list, say L.
  3. for each i,j in a[ ][ ]:
    { dist= INF for each x,y in L: { dist= min(dist,|i-x|+|j-y|) } a[i][j]= dist
    }
  4. Print a[ ][ ].

Optimized Approach:

Here’s the code:

--

--

--

Data Scientist, https://saikatkumardey.com

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Saikat Kumar Dey

Saikat Kumar Dey

Data Scientist, https://saikatkumardey.com

More from Medium

Active Record Finder Methods

CS373 Spring 2022 Week 11: Nathaniel Nemenzo

CS371p Spring 2022: Gautham Raju: Final Entry