문제:
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.
www.acmicpc.net
코드:
/* 1. rot는 move 4번과 별개로 돌려야 -> rot을 f(d,4) 밖으로 빼기*/
#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
#define f(i, b, e) for(int i = (b); i < (e); ++i)
using namespace std;
typedef pair<int, int> p;
bool map[52][52];
bool vst[50][50][2];
#define v(lg, tp) vst[(lg)[1].first][(lg)[1].second][(tp)]
int dr[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
int dc[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
void mov(vector<p> &lg, int d) {
for (auto&& p : lg) {
p.first += dr[d];
p.second += dc[d];
}
}
bool movable(vector<p> &lg) {
int ctr = 0;
for (auto p : lg)
if (map[p.first][p.second])
return false;
return true;
}
bool rotable(vector<p> &lg) {
int r = lg[1].first, c = lg[1].second;
f(d, 0, 8)
if (map[r + dr[d]][c + dc[d]])
return false;
return true;
}
vector<p> rot(vector<p> &lg, bool tp) {
int r = lg[1].first, c = lg[1].second;
if (tp) return { { r - 1, c },{ r, c },{ r + 1, c } };
else return { { r, c - 1 },{ r, c },{ r, c + 1 } };
}
struct qnode {
vector<p> lg;
bool tp; // -1 : not visited, 0 : ver, 1 : hor;
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N; cin >> N;
vector<p> str, ext;
fill(map[0], map[0] + N + 2, 1);
f(r, 1, N + 1) {
map[r][0] = map[r][N + 1] = 1;
f(c, 1, N + 1) {
char ch; cin >> ch;
switch (ch) {
case 'B': str.emplace_back(r, c); break;
case 'E': ext.emplace_back(r, c); break;
}
map[r][c] = (ch == '1');
}
}
fill(map[N + 1], map[N + 1] + N + 2, 1);
bool tp = str[0].first == str[1].first;
v(str, tp) = 1;
queue<qnode> q;
q.push({ str, tp });
int t = 0;
while (!q.empty()) {
int qs = q.size();
while (qs--) {
qnode pt = q.front(); q.pop();
if (pt.lg == ext)
goto out;
f(d, 0, 4) {
vector<p> clg = pt.lg;
mov(clg, d);
if (movable(clg) && !v(clg, pt.tp)) {
v(clg, pt.tp) = 1;
q.push({ clg, pt.tp });
}
}
if (rotable(pt.lg)) {
vector<p> clg = rot(pt.lg, pt.tp);
if (!v(clg, !pt.tp)) {
v(clg, !pt.tp) = 1;
q.push({ clg, !pt.tp });
}
}
}
++t;
}
t = 0;
out:
cout << t;
return 0;
}