백준 6226, bfs
USACO February 2007 Contest Silver 2번 문제.
각 지점마다 3가지의 정보를 한꺼번에 유지 해야한다.
어떤 지점 $(x,y)$ 로 이동하기 위해서 추가 해야하는 최소한의 정점 개수 $putpad$,
$putpad$ 만큼 정점 추가 했을때 최단거리 $distpad$,
위의 두 가지 조건이 주어졌을때 시작점에서 $(x,y)$ 까지 이동할 수 있는 경우의 수 $numbers$.
이 3가지 정보를 한꺼번에 update 하며 bfs 를 통해 최소 추가 - 최단 거리를 만족하는 경우의 수를 구한다.
각 정점의 상태를 한꺼번에 update 하고 유지한다는 발상 자체를 할 수가 없었다.
xiaowuc1 은 이동할 수 있는 최대 거리가 $30*30$ 으로 제한되어 있는점을 이용해서
$dp[row][col][num lilypads] = mininum distance$
$numw[30][30][900] = numbers$
로 정의하여 해결했다.
USACO 에서 제시하는 정해보다 조금 더 쉬운 방법인것 같다.
Source Code
//BOJ 6226
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define Msize 33
#define pii pair<int,int>
#define ll long long
int board[Msize][Msize];
bool chk[Msize][Msize];
pii pred[Msize][Msize];
int dist[Msize][Msize];
int N, M;
pii spoint, epoint;
int dx[8] = { -2,-2,-1,1,2,2,1,-1 };
int dy[8] = { -1,1,2,2,1,-1,-2,-2 };
bool isInside(int x, int y) {
if (x<1 || x>N || y<1 || y>M) return false;
else return true;
}
struct node {
int putpad, distpad;
ll numbers;
node() {
putpad = -1;
distpad = -1;
numbers = 0;
}
};
node cache[Msize][Msize];
queue<pii> q;
void updatecache(int nputpad, int nx, int ny, int x, int y) {
if (cache[nx][ny].putpad == -1 || nputpad < cache[nx][ny].putpad) {
cache[nx][ny].putpad = nputpad;
cache[nx][ny].distpad = cache[x][y].distpad + 1;
cache[nx][ny].numbers = cache[x][y].numbers;
if(!chk[nx][ny]){
chk[nx][ny] = true;
q.push({ nx,ny });
}
return;
}
if (cache[nx][ny].putpad != -1 && nputpad == cache[nx][ny].putpad && cache[nx][ny].distpad > cache[x][y].distpad + 1) {
cache[nx][ny].distpad = cache[x][y].distpad + 1;
cache[nx][ny].numbers = cache[x][y].numbers;
if (!chk[nx][ny]) {
chk[nx][ny] = true;
q.push({ nx,ny });
}
return;
}
if (cache[nx][ny].putpad != -1 && nputpad == cache[nx][ny].putpad && cache[nx][ny].distpad == (cache[x][y].distpad + 1)) {
cache[nx][ny].numbers += cache[x][y].numbers;
return;
}
}
void bfs() {
int x, y;
x = spoint.first, y = spoint.second;
cache[x][y].distpad = 0;
cache[x][y].putpad = 0;
cache[x][y].numbers = 1;
q.push(spoint);
while (!q.empty()) {
int x, y;
x = q.front().first, y = q.front().second;
q.pop();
chk[x][y] = true;
for (int i = 0; i < 8; ++i) {
int nx, ny;
nx = x + dx[i], ny = y + dy[i];
if (!isInside(nx, ny)) continue;
if (board[nx][ny] == 2) continue;
//if (chk[nx][ny]) continue;
int nputpad = cache[x][y].putpad + (board[nx][ny] == 1 ? 0 : 1);
updatecache(nputpad, nx, ny, x, y);
}
chk[x][y] = false;
}
}
void debug() {
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
printf("%3d ", cache[i][j].distpad);
}
printf("\n");
}
printf("\n");
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
printf("%3d ", cache[i][j].putpad);
}
printf("\n");
}
printf("\n");
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
printf("%3lld ", cache[i][j].numbers);
}
printf("\n");
}
}
int main() {
cin >> N >> M;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
cin >> board[i][j];
if (board[i][j] == 3) {
spoint = { i,j };
board[i][j] = 1;
}
if (board[i][j] == 4) {
board[i][j] = 1;
epoint = { i,j };
}
}
}
memset(chk, 0, sizeof(chk));
bfs();
//debug();
if (cache[epoint.first][epoint.second].distpad == -1) printf("-1\n");
else {
printf("%d\n", cache[epoint.first][epoint.second].putpad);
printf("%d\n", cache[epoint.first][epoint.second].distpad);
printf("%lld\n", cache[epoint.first][epoint.second].numbers);
}
return 0;
}