[백준] 8061-Bitmap

문제링크:https://www.acmicpc.net/problem/8061

8061번: Bitmap

 

전형적인 bfs 문제입니다. d(p1,p2)=|i1-i2|+|j1-j2| 을 만족하는 최단 경로 탐색문제입니다.

너무 쉬워서 설명은 생략하겠습니다.

 

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int n = 0, m = 0;
int arr[183][183] = { 0 };
int visited[183][183] = { 0 };
int que[40000][2] = { 0 };
int started = 0, ended = 0;
int x_go[4] = { 0,0,1,-1 };
int y_go[4] = { 1,-1,0,0 };

void bfs() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (arr[i][j] == 1)
				que[ended][0] = i, que[ended++][1] = j, visited[i][j] = 1;

	while (started != ended) {
		int y = que[started][0];
		int x = que[started++][1];

		for (int i = 0; i < 4; i++) {
			int yyy = y + y_go[i];
			int xxx = x + x_go[i];
			if (yyy >= 0 && yyy < n && xxx >= 0 && xxx < m)
				if (!visited[yyy][xxx]) {
					visited[yyy][xxx] = visited[y][x] + 1;
					que[ended][0] = yyy, que[ended++][1] = xxx;
				}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string arg;
		cin >> arg;
		for (int j = 0; j < m; j++) {
			arr[i][j] = arg[j] - '0';

		}
	}

	bfs();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << visited[i][j] - 1 << ' ';
		cout << '\n';
	}
}

 

 그리고 조금더 오래걸리지만 브루트포스의 형식으로도 solve를 받을 수 있습니다.

장점: 쉬운 문제풀이 단점: 시간 

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int n = 0, m = 0;
int arr[183][183] = { 0 };
int visited[183][183] = { 0, };
int que[40000][2] = { 0 };
int ended = 0;

void func() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (arr[i][j] == 1)
				que[ended][0] = i, que[ended++][1] = j;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			int y = i, x = j;

			for (int k = 0; k < ended; k++) {
				if (arr[y][x] == 0) {
					int val = abs(y - que[k][0]) + abs(x - que[k][1]);
					if (visited[y][x] > val) {
						visited[y][x] = val;
					}
				}
			}

		}

}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string arg;
		cin >> arg;
		for (int j = 0; j < m; j++) {
			arr[i][j] = arg[j] - '0';
			if (arr[i][j] == 0)
				visited[i][j] = 1000;
		}
	}

	func();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout << visited[i][j] << ' ';
		cout << '\n';
	}
}