Algorithm
Problem link- https://www.spoj.com/problems/BITMAP/
BITMAP - Bitmap
There is given a rectangular bitmap of size n*m. Each pixel of the bitmap is either white or black, but at least one is white. The pixel in i-th line and j-th column is called the pixel (i,j). The distance between two pixels p1=(i1,j1) and p2=(i2,j2) is defined as:
Task
Write a program which:
- reads the description of the bitmap from the standard input,
- for each pixel, computes the distance to the nearest white pixel,
- writes the results to the standard output.
Input
The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case there is a pair of integer numbers n, m separated by a single space, 1<=n <=182, 1<=m<=182. In each of the following n lines of the test case exactly one zero-one word of length m, the description of one line of the bitmap, is written. On the j-th position in the line (i+1), 1 <= i <= n, 1 <= j <= m, is '1' if, and only if the pixel (i,j) is white.
Output
In the i-th line for each test case, 1<=i<=n, there should be written m integers f(i,1),...,f(i,m) separated by single spaces, where f(i,j) is the distance from the pixel (i,j) to the nearest white pixel.
Example
Sample input: 1 3 4 0001 0011 0110 Sample output: 3 2 1 0 2 1 0 0 1 0 0 1
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
using namespace std;
string a[200];
int ans[200][200], q[200 * 200 * 2], n, m, s;
int dx[] = {0 , 0 , 1 , -1}, dy[] = {1 , -1, 0 , 0};
void bfs()
{
for(int i=0;i<s;i+=2)
{
int cx=q[i];
int cy=q[i+1];
for(int j=0;j<4;j++)
{
int xx=cx+dx[j];
int yy=cy+dy[j];
if(xx < 0 || yy < 0 || xx >= n || yy >= m || ans[xx][yy] != -1) continue;
ans[xx][yy] = ans[cx][cy] + 1;
q[s++] = xx;
q[s++] = yy;
}
}
for(int i = 0; i < n ; i++)
{
for(int j = 0; j < m; j++)
cout << ans[i][j] << " ";
cout << endl;
}
}
int main()
{
long long t;
cin>>t;
while(t--)
{
memset(ans, 255, sizeof ans);
s=0;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
for(int j=0;j<m;j++)
{
if(a[i][j]=='1')
{
ans[i][j]=0;
q[s++]=i;
q[s++]=j;
}
}
}
bfs();
}
}Input
3 4
0001
0011
0110
Output
2 1 0 0
1 0 0 1
#2 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
class BITMAP{
public static void main(String[] args) throws Exception{
Parser in = new Parser(System.in);
StringBuilder string = new StringBuilder();
int num = in.nextInt();
for(int z = 0; z < num; z++){
int rows = in.nextInt();
int cols = in.nextInt();
char[][] grid = new char[rows+2][cols+2];
int[][] result = new int[rows+2][cols+2];
int[] xValues = {1, -1, 0, 0};
int[] yValues = {0, 0, 1, -1};
for(int a = 0; a < cols+2; a++){
grid[0][a] = '#';
grid[rows+1][a] = '#';
}
Queue<Bit> queue = new LinkedList<Bit>();
Bit current = null;
boolean[][]visited = new boolean[rows+2][cols+2];
for(int j = 1; j < rows+1; j++){
String line = in.next();
grid[j][0] = '#';
for(int k = 1; k < cols+1; k++){
grid[j][k] = line.charAt(k-1);
result[j][k] = 500;
if(grid[j][k] == '1'){
queue.add(new Bit(j,k,0));
visited[j][k] = true;
}
}
grid[j][cols+1] = '#';
}
while(!queue.isEmpty()){
current = queue.remove();
result[current.x][current.y] = Math.min(current.distance, result[current.x][current.y]);
for(int m = 0; m < 4; m++){
int x = current.x+xValues[m];
int y = current.y+yValues[m];
if(!visited[x][y] && grid[x][y] != '#'){
queue.add(new Bit(x,y,current.distance+1));
visited[x][y] = true;
}
}
}
for(int rowNum = 1; rowNum < rows+1; rowNum++){
for(int colNum = 1; colNum < cols+1; colNum++){
if(colNum == cols){
string.append(result[rowNum][colNum] + "\n");
}else{
string.append(result[rowNum][colNum] + " ");
}
}
}
string.append("\n");
}
System.out.print(string);
}
static class Bit{
public int x;
public int y;
public int distance;
public Bit(int x, int y, int distance){
this.x = x;
this.y = y;
this.distance = distance;
}
}
}
class Parser
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Parser(InputStream in)
{
din = new DataInputStream(in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public long nextLong() throws Exception
{
long ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = c == '-';
if (neg) c = read();
do
{
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg) return -ret;
return ret;
}
//reads in the next string
public String next() throws Exception
{
StringBuilder ret = new StringBuilder();
byte c = read();
while (c <= ' ') c = read();
do
{
ret = ret.append((char)c);
c = read();
} while (c > ' ');
return ret.toString();
}
public int nextInt() throws Exception
{
int ret = 0;
byte c = read();
while (c <= ' ') c = read();
boolean neg = c == '-';
if (neg) c = read();
do
{
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg) return -ret;
return ret;
}
private void fillBuffer() throws Exception
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1) buffer[0] = -1;
}
private byte read() throws Exception
{
if (bufferPointer == bytesRead) fillBuffer();
return buffer[bufferPointer++];
}
}Input
3 4
0001
0011
0110
Output
2 1 0 0
1 0 0 1
Demonstration
SPOJ Solution-Bitmap-Solution in C, C++, Java, Python