一.题目链接：
POJ-3322
二.题目大意：
翻砖块：体验
三.分析：
题目不难，把所用东西搞清楚就行了.
这里多写了一个打印路径的，供以后 玩 学习.
四.代码实现：
一.AC 版本
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;
const int M = (int)5e2;
const int mod = 99991;
const int inf = 0x3f3f3f3f;
int n, m;
char s[M + 5][M + 5];
struct node
{
int x, y, lie;
}st, ed, p, t;
queue <node> q;
///右左下上
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int step[M + 5][M + 5][3];
int next_x[3][4] =
{
{0, 0, 1, -2},
{0, 0, 1, -1},
{0, 0, 2, -1}
};
int next_y[3][4] =
{
{1, -2, 0, 0},
{2, -1, 0, 0},
{1, -1, 0, 0}
};
int next_lie[3][4] =
{
{1, 1, 2, 2},
{0, 0, 1, 1},
{2, 2, 0, 0}
};
bool valid(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void parse_st_ed()
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(s[i][j] == 'O')
ed.x = i, ed.y = j, ed.lie = 0, s[i][j] = '.';
else if(s[i][j] == 'X')
{
st.x = i, st.y = j, st.lie = 0, s[i][j] = '.';
for(int k = 0; k < 4; k += 2)
{
int x = i + dx[k], y = j + dy[k];
if(valid(x, y) && s[x][y] == 'X')
{
st.lie = k / 2 + 1;
s[x][y] = '.';
break;
}
}
}
}
}
}
bool valid(struct node t)
{
if(!valid(t.x, t.y)) return 0;
if(~step[t.x][t.y][t.lie]) return 0;
if(s[t.x][t.y] == '#') return 0;
if(t.lie == 0 && s[t.x][t.y] != '.') return 0;
if(t.lie == 1 && (!valid(t.x, t.y + 1) || s[t.x][t.y + 1] == '#')) return 0;
if(t.lie == 2 && (!valid(t.x + 1, t.y) || s[t.x + 1][t.y] == '#')) return 0;
return 1;
}
int bfs()
{
memset(step, -1, sizeof(step));
step[st.x][st.y][st.lie] = 0;
while(!q.empty()) q.pop();
q.push(st);
while(!q.empty())
{
p = q.front();
q.pop();
for(int i = 0; i < 4; ++i)
{
t = p;
t.x += next_x[t.lie][i];
t.y += next_y[t.lie][i];
t.lie = next_lie[t.lie][i];
if(valid(t))
{
step[t.x][t.y][t.lie] = step[p.x][p.y][p.lie] + 1;
if(t.x == ed.x && t.y == ed.y && t.lie == ed.lie)
return step[t.x][t.y][t.lie];
q.push(t);
}
}
}
return -1;
}
int main()
{
while(~scanf("%d %d", &n, &m) && (n + m))
{
for(int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
parse_st_ed();
int ans = bfs();
if(~ans)
printf("%d\n", ans);
else
printf("Impossible\n");
}
return 0;
}
二.打印路径版本
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long
#define ull unsigned long long
using namespace std;
const int M = (int)5e2;
const int mod = 99991;
const int inf = 0x3f3f3f3f;
int n, m;
char s[M + 5][M + 5];
struct node
{
int x, y, lie;
} st, ed, p, t, fa[M + 5][M + 5][3];
queue <node> q;
///右左下上
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int step[M + 5][M + 5][3];
int next_x[3][4] =
{
{0, 0, 1, -2},
{0, 0, 1, -1},
{0, 0, 2, -1}
};
int next_y[3][4] =
{
{1, -2, 0, 0},
{2, -1, 0, 0},
{1, -1, 0, 0}
};
int next_lie[3][4] =
{
{1, 1, 2, 2},
{0, 0, 1, 1},
{2, 2, 0, 0}
};
bool valid(int x, int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void parse_st_ed()
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(s[i][j] == 'O')
ed.x = i, ed.y = j, ed.lie = 0, s[i][j] = '.';
else if(s[i][j] == 'X')
{
st.x = i, st.y = j, st.lie = 0, s[i][j] = '.';
for(int k = 0; k < 4; k += 2)
{
int x = i + dx[k], y = j + dy[k];
if(valid(x, y) && s[x][y] == 'X')
{
st.lie = k / 2 + 1;
s[x][y] = '.';
break;
}
}
}
}
}
}
bool valid(struct node t)
{
if(!valid(t.x, t.y))
return 0;
if(~step[t.x][t.y][t.lie])
return 0;
if(s[t.x][t.y] == '#')
return 0;
if(t.lie == 0 && s[t.x][t.y] != '.')
return 0;
if(t.lie == 1 && (!valid(t.x, t.y + 1) || s[t.x][t.y + 1] == '#'))
return 0;
if(t.lie == 2 && (!valid(t.x + 1, t.y) || s[t.x + 1][t.y] == '#'))
return 0;
return 1;
}
int bfs()
{
memset(step, -1, sizeof(step));
step[st.x][st.y][st.lie] = 0;
while(!q.empty())
q.pop();
q.push(st);
while(!q.empty())
{
p = q.front();
q.pop();
for(int i = 0; i < 4; ++i)
{
t = p;
t.x += next_x[t.lie][i];
t.y += next_y[t.lie][i];
t.lie = next_lie[t.lie][i];
if(valid(t))
{
step[t.x][t.y][t.lie] = step[p.x][p.y][p.lie] + 1;
fa[t.x][t.y][t.lie] = p;
if(t.x == ed.x && t.y == ed.y && t.lie == ed.lie)
return step[t.x][t.y][t.lie];
q.push(t);
}
}
}
return -1;
}
/**
9 14
###EEEEEEE####
###EEEEEEE####
....#####...##
...#######..##
...#######..##
.X.##....EEEEE
...##....EEEEE
#####.O.##EE.E
#####...##EEEE
0 0
**/
void print_solution()
{
stack <node> Stack;
p = ed;
Stack.push(p);
while(p.x != st.x || p.y != st.y || p.lie != st.lie)
{
p = fa[p.x][p.y][p.lie];
Stack.push(p);
}
p = Stack.top(), Stack.pop();
getchar();
for(int step = 1; !Stack.empty(); ++step)
{
printf("%2d.", step);
t = Stack.top(), Stack.pop();
for(int i = 0; i < 4; ++i)
{
if(p.x + next_x[p.lie][i] == t.x && p.y + next_y[p.lie][i] == t.y && next_lie[p.lie][i] == t.lie)
{
switch(i)
{
case 0: printf("右");break;
case 1: printf("左");break;
case 2: printf("下");break;
case 3: printf("上");break;
}
break;
}
}
printf("：(%d,%d,%d)->(%d,%d,%d)\n", p.x, p.y, p.lie, t.x, t.y, t.lie);
p = t;
if(step % 5 == 0) getchar();
}
}
int main()
{
while(~scanf("%d %d", &n, &m) && (n + m))
{
for(int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
parse_st_ed();
int ans = bfs();
if(~ans)
{
printf("%d\n", ans);
print_solution();
}
else
printf("Impossible\n");
}
return 0;
}
京公网安备 11010502036488号