<유사문제>
13460 째로탈출 https://www.acmicpc.net/problem/13460
풀이 : https://lyzqm.blogspot.kr/2017/04/13460-2.html
11559 Puyo Puyo https://www.acmicpc.net/problem/11559
2933 미네랄 https://www.acmicpc.net/problem/2933
(Puyo Puyo와 굉장히 유사한 문제이다.
미네랄을 통째로 떨어뜨리는 것과 뿌요를 빈공간없이 떨어뜨리는것의 차이)
9207 페그 솔리테어 https://www.acmicpc.net/problem/9207
1. Ricochet Robots
이 문제에서는 방문배열 대신 로봇들의 좌표를 map이나 set에 넣어 방문여부를 판단한다.
로봇들이 한칸씩 이동하는것이 아닌 일단 움직이면 끝까지(장애물이있거나 맵 테두리)
가기때문에 위치를 잘 판단하게끔 만드는것이 중요하다.
<만든 테스트 케이스>
4 5 4 10
.....
.X.W.
WWW..
2314.
7
4 5 4 10
.....
.X.W.
WWW..
2134.
8
4 5 4 10
.....
.X.W.
WWW..
2431.
8
4 5 4 10
.....
X..W.
WWW..
2431.
4
4 5 4 4
.....
X..W.
WWW..
2431.
4
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
typedef pair<pair<int, int>, pair<int, int> > MP;
#define mp(a,b) make_pair(a,b)
#define mf(a,b,c,d) mp(mp(a,b),mp(c,d))
int N, M, R, L;
char arr[11][11];
int robot[4];
int goal;
map<MP,int> seen;
struct Pos{
int y, x;
void append(int site){
y = site / M;
x = site % M;
}
};
void Push(int num, int next, int moves, queue<MP> &q){
MP p;
if (num == 0) p = mf(next, q.front().first.second, q.front().second.first, q.front().second.second);
else if (num == 1) p = mf(q.front().first.first, next, q.front().second.first, q.front().second.second);
else if (num == 2) p = mf(q.front().first.first, q.front().first.second, next, q.front().second.second);
else if (num == 3) p = mf(q.front().first.first, q.front().first.second, q.front().second.first, next);
if (seen.find(p) == seen.end()) {
q.push(p);
seen[p] = moves;
}
}
int bfs(){
int ans = 0;
int dy[] = { -1, 0, 0, 1 }, dx[] = { 0, 1, -1, 0 };
queue<MP> q; //좌표, 로봇번호
q.push(mf(robot[0],robot[1],robot[2],robot[3]));
while (!q.empty()){
int sz = q.size();
for (int s = 0; s < sz; s++){
Pos curr[4];
curr[0].append(q.front().first.first), curr[1].append(q.front().first.second),
curr[2].append(q.front().second.first), curr[3].append(q.front().second.second);
if (curr[0].y * M + curr[0].x == goal) return ans;
for (int r = 0; r < R; r++){
int y = curr[r].y, x = curr[r].x;
for (int i = 0; i < 4; i++){
int ny = y, nx = x;
while (1){
bool f = false;
ny += dy[i], nx += dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M || arr[ny][nx] == 'W') break;
for (int rr = 0; rr < R; rr++){
if (rr == r) continue;
if (ny == curr[rr].y && nx == curr[rr].x){ f = true; break; }
}
if (f) break;
}
ny -= dy[i], nx -= dx[i];
if (ny == y && nx == x) continue;
int next = ny*M + nx;
Push(r, next, ans, q);
}
}
q.pop();
}
ans++;
if (ans > L) return -1;
}
return -1;
}
int main(){
scanf("%d%d%d%d", &R, &M, &N, &L);
for (int n = 0; n < N; n++)
for (int m = 0; m < M; m++){
scanf(" %1c", &arr[n][m]);
if (arr[n][m] == 'X'){
goal = n*M + m;
arr[n][m] = '.';
}
for (int r = 1; r <= R; r++){
if (arr[n][m] - '0' == r){
robot[r - 1] = n*M + m;
arr[n][m] = '.';
}
}
}
int ans = bfs();
if (ans == -1) printf("NO SOLUTION\n");
else printf("%d\n", ans);
return 0;
}
| cs |
2. Puyo Puyo
정말 게임문제이다. (뿌요뿌요,테트리스)
한 타임에 터질 뿌요가 여러개일 경우 뿌요들을 다 터뜨린 후에 중력의 영향을 받게해야한다.
또한 중력의 영향을 받아 밑으로 떨어질때를 잘 구현해야한다.
(이 부분에서 틀렸음)
#include <cstdio>
#include <queue>
using namespace std;
char map[14][8];
int visit[14][8];
int group = 1;
void clear(){
for (int i = 0; i<12; i++)
for (int j = 0; j<6; j++)
if (visit[i][j] == group)
map[i][j] = '.';
}
int bfs(int iy, int ix){
int dy[4] = { -1, 0, 0, 1 }, dx[4] = { 0, 1, -1, 0 };
int cnt = 1;
queue<int> q;
q.push(iy * 6 + ix);
visit[iy][ix] = group;
while (!q.empty()){
int sz = q.size();
for (int s = 0; s < sz; s++){
int y = q.front() / 6, x = q.front() % 6;
q.pop();
for (int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= 12 || nx < 0 || nx >= 6 || visit[ny][nx] > 0) continue;
if (map[ny][nx] == map[iy][ix]){
q.push(ny * 6 + nx);
visit[ny][nx] = group;
cnt++;
}
}
}
}
return cnt;
}
int main(){
for (int n = 0; n < 12; n++)
scanf("%s", map[n]);
int ans = 0;
while (1){
bool flag = false;
for (int n = 0; n < 12; n++){
for (int m = 0; m < 6; m++){
if (!visit[n][m] && map[n][m] != '.'){
if (bfs(n, m) >= 4)
flag = true, clear();
group++;
}
}
}
if (flag){
ans++;
for (int i = 0; i < 6; i++){
for (int j = 11; j >= 0; j--)
{
int x = j, y = i;
if (map[x][y] != '.')
{
x++;
while (x < 12 && map[x][y] == '.') swap(map[x][y], map[x - 1][y]), x++;
}
}
}
}
else break;
for (int n = 0; n < 12; n++)
for (int m = 0; m < 6; m++)
visit[n][m] = 0;
}
printf("%d\n", ans);
return 0;
}
| cs |
3. 페그 솔리테어
map의 형태가 pin위치를 제외하고 고정되있으며 map또한 작다.
pin의 위치정보를 queue에 넣어 bfs탐색하며 인접한 pin이 있을 시 처리를 해준다.
방문여부는 set에 pin정보들을 넣어 판단한다. (pin들의 정보는 vector형태로 담겨있는데 정렬을 한다음에 넣어야 중복되는것이 없다)
이 문제에서는 방문여부를 확인안해도 워낙 경우가 작아 AC된다. (dfs로 풀어도 AC)
#include <cstdio>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define INF 987654321
#define MAX_N 5
#define MAX_M 9
int ans;
int buf[MAX_N * MAX_M];
char arr[MAX_N][MAX_M];
int bfs(vector<int> &input){
int move = 0;
int dy[] = { -1, 0, 0, 1 }, dx[] = { 0, 1, -1, 0 };
set<vector<int>> visit;
queue<vector<int>> q;
sort(input.begin(), input.end());
q.push(input);
visit.insert(input);
while (!q.empty()){
int sz = q.size();
for (int s = 0; s < sz; s++){
vector<int> pin = q.front();
int psize = pin.size();
q.pop();
ans = min(ans, psize);
buf[ans] = min(buf[ans], move);
if (psize == 1)
return 1;
char map[MAX_N + 1][MAX_M + 1] = { { "###...###" },
{ "........." },
{ "........." },
{ "........." },
{ "###...###" }};
for (int n : pin) map[n / MAX_M][n % MAX_M] = 'o';
for (int n = 0; n < pin.size(); ++n){
int y = pin[n] / MAX_M, x = pin[n] % MAX_M;
for (int i = 0; i < 4; i++){
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= MAX_N || nx < 0 || nx >= MAX_M) continue;
if (map[ny][nx] == 'o'){ //pin[n] 과 ny,nx 는 인접
if (ny + dy[i] >= 0 && ny + dy[i] < MAX_N && nx + dx[i] >= 0 && nx + dx[i] < MAX_M &&
map[ny + dy[i]][nx + dx[i]] == '.'){
vector<int> newpin;
for (int t = 0; t < pin.size();++t){
if (t == n || (pin[t] / MAX_M == ny && pin[t] % MAX_M == nx)) continue;
newpin.push_back(pin[t]);
}
newpin.push_back((ny + dy[i]) * MAX_M + nx + dx[i]);
sort(newpin.begin(), newpin.end());
if (visit.find(newpin) == visit.end()){
q.push(newpin);
visit.insert(newpin);
}
}
}
}
}
}
move++;
}
return ans;
}
int main(){
int T;
scanf("%d", &T);
while (T--){
ans = INF;
fill(buf, buf + MAX_N*MAX_M, INF);
vector<int> pin;
for (int n = 0; n < MAX_N; n++){
for (int m = 0; m < MAX_M; m++){
scanf(" %1c", &arr[n][m]);
if (arr[n][m] == 'o')
pin.push_back( n * MAX_M + m);
}
}
int ret = bfs(pin);
printf("%d %d\n", ret, buf[ret]);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기