广度优先搜索
感悟：这类题目的基本框架还是很简单的，剪枝都不用思考很多。但状态的表示是个难题，特别的麻烦，只能先总结点大概的处理思路。这题我是想不到这么好的处理方式，特别是三维数组都不是很会用，刷完搜索就去刷刷数据结构类的题吧。
本题是个单源最短路径的问题
广搜的基本框架（bfs）
- 题目所给的所有状态的表示
- 开始与结束状态的储存
- 基本四个方向的表示
- 每走一步状态的储存
int bfs()
{
queue<> q;
q.push(start);//起始点先入队列
while(q.size())
{
auto t = q.front(); q.pop();//队头出来执行命令
for(int i = 0; i < 4; i++)//循环四个方向走
{
if(!check()) ; //判重，检查
if() q.push(); //满足条件，则入队
}
}
return ;
}
本题思路
- 1.把图存起来；2.箱子可立可躺，躺又可横可竖，三种状态。
- 三种状态表示，特别是躺的，最好找准一个基点（左上），不然很难处理
struct State{ int x, y, s;};//s = 0立 1横 2竖
- 找开始与结束，开始分三种，都用State存好
- 四个方向的表示关键是加了一个状态，用三维数组处理
- 每一步的表示也是多一个状态，三维数组
ACcode
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 505;
struct State{
int x, y, s;
};
int n, m;
char g[N][N];
int dist[N][N][3];
bool check(int x, int y)
{
if(x < 0 || x >= n || y < 0 || y >= m) return false;
if(g[x][y] == '#') return false;
return true;
}
int bfs(State start, State end)
{
queue<State> q;
memset(dist, -1, sizeof(dist));
dist[start.x][start.y][start.s] = 0;
q.push(start);
int d[3][4][3] = { //三个状态，四个方向，走完后的三种状态之一
{{-2, 0, 2}, {0, 1, 1}, {1, 0, 2}, {0, -2, 1}},
{{-1, 0, 1}, {0, 2, 0}, {1, 0, 1}, {0, -1, 0}},
{{-1, 0, 0}, {0, 1, 2}, {2, 0, 0}, {0, -1, 2}}
};
while(q.size())
{
auto t = q.front(); //这里的auto就是State
q.pop();
for(int i = 0; i< 4; i++)
{
State next = {t.x+d[t.s][i][0], t.y+d[t.s][i][1], d[t.s][i][2]};
int x = next.x, y = next.y;
if(!check(x, y)) continue; //检查这一个点
if(next.s == 0) { //立的不能在‘E’
if(g[x][y] == 'E') continue;
}
else if(next.s == 1) { //横的第二个位置
if(!check(x, y+1)) continue;
}
else { //竖的第二个位置
if(!check(x+1, y)) continue;
}
if(dist[next.x][next.y][next.s] == -1)
{
dist[next.x][next.y][next.s] = dist[t.x][t.y][t.s] + 1;
q.push(next);
}
}
}
return dist[end.x][end.y][end.s];
}
int main()
{
while(scanf("%d%d", &n, &m), n || m)
{
for(int i = 0; i < n; i++) scanf("%s", g[i]);
State start = { -1 }, end;
for(int i = 0; i < n; i++) //储存开始，结束状态
for(int j = 0; j < m; j++)
if(g[i][j] == 'X' && start.x == -1)
{
if(g[i+1][j] == 'X') start = {i, j, 2};
else if(g[i][j+1] == 'X') start = {i, j, 1};
else start = {i, j, 0};
}
else if(g[i][j] == 'O') end = {i, j, 0};
int cnt = bfs(start, end);
if(cnt == -1) printf("Impossible\n");
else printf("%d\n", cnt);
}
return 0;
}
