ZJ5. 编程题1
描述
..S0.. -> ...S0.
注意不能将箱子推动到'#'上, 也不能将箱子推出边界;
现在, 给你游戏的初始样子, 你需要输出最少几步能够完成游戏, 如果不能完成, 则输出-1。
输入描述
第一行为2个数字,n, m, 表示游戏盘面大小有n 行m 列(5< n, m < 50);输出描述
一个数字,表示最少几步能完成游戏,如果不能,输出-1;示例1
输入:
3 6 .S#..E .#.0.. ......
输出:
11
C++ 解法, 执行用时: 3ms, 内存消耗: 2168KB, 提交时间: 2020-08-17
#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <ctime>
using namespace std;
#define maxn 55
int n, m;
char board[maxn][maxn];
struct point {
int x;
int y;
point() : x(), y() {} // 无参构造函数
point(int a, int b) : x(a), y(b) {} // 有参构造函数
};
point start, expect, original;
bool visited[maxn][maxn][maxn][maxn];
struct Node {
int person_x, person_y, box_x, box_y, step, weight;
bool operator < (const Node& temp) const { // 重载，优先级
return temp.weight + abs(temp.person_x - temp.box_x) + abs(temp.person_y - temp.box_y) + temp.step
< weight + abs(person_x - box_x) + abs(person_y - box_y) + step;
}
};
Node tmp;
int direction[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
bool judge(int x, int y) {
if (x >= 1 && x <= n && y >= 1 && y <= m && board[x][y] != '#') {
return true;
}
return false;
}
int bfs() {
tmp = { start.x, start.y, original.x, original.y, 0, 0 };
priority_queue<Node> queue;
queue.push(tmp);
visited[start.x][start.y][original.x][original.y] = 1;
while (!queue.empty()) {
Node cur = queue.top();
//cout << cur.person_x << ", " << cur.person_y << endl;
queue.pop();
if (cur.box_x == expect.x && cur.box_y == expect.y) { // 箱子成功推到预期位置
return cur.step;
}
for (int i = 0; i < 4; i++) {
int person_x = cur.person_x + direction[i][0];
int person_y = cur.person_y + direction[i][1];
int box_x = cur.box_x;
int box_y = cur.box_y;
if (person_x == box_x && person_y == box_y) { // 碰到箱子就推箱子
box_x += direction[i][0];
box_y += direction[i][1];
}
if (!judge(person_x, person_y) || !judge(box_x, box_y)) {
continue;
}
if (visited[person_x][person_y][box_x][box_y] == 1) {
continue;
}
visited[person_x][person_y][box_x][box_y] = 1;
queue.push({person_x, person_y, box_x, box_y, cur.step + 1, abs(expect.x - box_x) + abs(expect.y - box_y)});
}
}
return -1;
}
int main() {
cin >> n >> m;
string str;
for (int i = 1; i <= n; i++) {
cin >> str;
for (int j = 1; j <= m; j++) {
board[i][j] = str[j - 1];
if (board[i][j] == 'S') {
start = { i, j };
}
else if (board[i][j] == '0') {
original = { i, j };
}
else if (board[i][j] == 'E') {
expect = { i, j };
}
}
}
cout << bfs() << endl;
system("pause");
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 2184KB, 提交时间: 2020-08-08
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <unordered_map>
#include <limits.h>
#include <queue>
using namespace std;
const int N = 55;
bool vis[N][N][N][N]; /// vis[a][b][c][d] 表示人在 (a,b)处,
char graph[N][N];
int n, m, px, py, boxx, boxy, ex, ey;
struct Node
{
int px, py, boxx, boxy, step, weight;
bool operator<(const Node &rs) const
{ /// 重载, step大的Node优先级小
return rs.weight + abs(rs.px - rs.boxx) + abs(rs.py - rs.boxy) + rs.step < weight + abs(px - boxx) + abs(py - boxy) + step;
}
} s;
/*
struct Node
{
int px, py, boxx, boxy, step;
bool operator<(const Node &rs) const
{ /// 重载, step大的Node优先级小
return rs.step < step;
}
} s;*/
int dir[][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool judge(int x, int y)
{
if (x < 0 || x >= n || y < 0 || y >= m || graph[x][y] == '#')
return false;
return true;
}
int bfs()
{
s = {px, py, boxx, boxy, 0, 0};
priority_queue<Node> q;
q.push(s);
vis[px][py][boxx][boxy] = 1;
while (!q.empty())
{
Node u = q.top();
q.pop();
//printf("%d %d %d %d\n",u.px,u.py,u.boxx,u.boxy);
if (u.boxx == ex && u.boxy == ey)
return u.step;
for (int i = 0; i < 4; i++)
{
int pxx = u.px + dir[i][0];
int pyy = u.py + dir[i][1]; /// 人往该方向走了一步
int boxx = u.boxx, boxy = u.boxy;
if (pxx == boxx && pyy == boxy)
{ /// 碰到了箱子则将箱子向外推动一格
boxx += dir[i][0];
boxy += dir[i][1];
}
if (!judge(pxx, pyy) || !judge(boxx, boxy))
continue;
if (vis[pxx][pyy][boxx][boxy])
continue;
vis[pxx][pyy][boxx][boxy] = 1;
auto weight = abs(ex - boxx) + abs(ey - boxy);
q.push({pxx, pyy, boxx, boxy, u.step + 1, weight});
}
}
return -1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%s", graph[i]);
for (int j = 0; j < m; j++)
{
if (graph[i][j] == '0')
boxx = i, boxy = j, graph[i][j] = '.';
if (graph[i][j] == 'S')
px = i, py = j, graph[i][j] = '.';
if (graph[i][j] == 'E')
ex = i, ey = j, graph[i][j] = '.';
}
}
printf("%d\n", bfs());
system("pause");
return 0;
}
C++ 解法, 执行用时: 4ms, 内存消耗: 1920KB, 提交时间: 2020-08-18
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <unordered_map>
#include <limits.h>
#include <queue>
using namespace std;
const int maxmn=55;
bool arrival [maxmn][maxmn][maxmn][maxmn];
char mymap[maxmn][maxmn];
int n=0,m=0,sx=0,sy=0,bx=0,by=0,ex=0,ey=0;
struct PosInfo{
int sx, sy, bx,by,step, weight;
bool operator <(const PosInfo& pi)const{
int val1=pi.weight+
abs(pi.sx-pi.bx)+
abs(pi.sy-pi.by)+
pi.step;
int val2=weight+
abs(sx-bx)+
abs(sy-by)+
step;
return val1 < val2;
}
};
int dir[][2]={1,0,-1,0,0,1,0,-1};
bool check(int x,int y) {
if(x<0||y<0||x>=n||y>=m||mymap[x][y]=='#')
return false;
return true;
}
int bfs(){
priority_queue<PosInfo> queue1;
queue1.push({sx,sy,bx,by,0,0});
arrival[sx][sy][bx][by] = true;
while(!queue1.empty()){
PosInfo posinfo=queue1.top();
queue1.pop();
if(ex==posinfo.bx&&ey==posinfo.by) return posinfo.step;
for(int i=0;i<4;i++){
int tsx=posinfo.sx+dir[i][0];
int tsy=posinfo.sy+dir[i][1];
int tbx=posinfo.bx;
int tby=posinfo.by;
if(tsx==tbx&&tsy==tby){
tbx+=dir[i][0];
tby+=dir[i][1];
}
if(!check(tsx,tsy)||!check(tbx,tby)) continue;
if(arrival[tsx][tsy][tbx][tby]) continue;
arrival[tsx][tsy][tbx][tby]=true;
int weight=abs(ex-tbx)+abs(ey-tby);
queue1.push({tsx,tsy,tbx,tby,posinfo.step+1,weight});
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>mymap[i][j];
if(mymap[i][j]=='S'){
sx=i;
sy=j;
}
if(mymap[i][j]=='0'){
bx=i;
by=j;
}
if(mymap[i][j]=='E'){
ex=i;
ey=j;
}
}
}
cout<<bfs()<<endl;
return 0;
}
C++ 解法, 执行用时: 4ms, 内存消耗: 2168KB, 提交时间: 2020-08-10
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <unordered_map>
#include <limits.h>
#include <queue>
using namespace std;
const int N = 55;
bool vis[N][N][N][N]; /// vis[a][b][c][d] 表示人在 (a,b)处,
char graph[N][N];
int n, m, px, py, boxx, boxy, ex, ey;
struct Node
{
int px, py, boxx, boxy, step, weight;
bool operator<(const Node &rs) const
{ /// 重载, step大的Node优先级小
return rs.weight + abs(rs.px - rs.boxx) + abs(rs.py - rs.boxy) + rs.step < weight + abs(px - boxx) + abs(py - boxy) + step;
}
} s;
/*
struct Node
{
int px, py, boxx, boxy, step;
bool operator<(const Node &rs) const
{ /// 重载, step大的Node优先级小
return rs.step < step;
}
} s;*/
int dir[][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool judge(int x, int y)
{
if (x < 0 || x >= n || y < 0 || y >= m || graph[x][y] == '#')
return false;
return true;
}
int bfs()
{
s = {px, py, boxx, boxy, 0, 0};
priority_queue<Node> q;
q.push(s);
vis[px][py][boxx][boxy] = 1;
while (!q.empty())
{
Node u = q.top();
q.pop();
//printf("%d %d %d %d\n",u.px,u.py,u.boxx,u.boxy);
if (u.boxx == ex && u.boxy == ey)
return u.step;
for (int i = 0; i < 4; i++)
{
int pxx = u.px + dir[i][0];
int pyy = u.py + dir[i][1]; /// 人往该方向走了一步
int boxx = u.boxx, boxy = u.boxy;
if (pxx == boxx && pyy == boxy)
{ /// 碰到了箱子则将箱子向外推动一格
boxx += dir[i][0];
boxy += dir[i][1];
}
if (!judge(pxx, pyy) || !judge(boxx, boxy))
continue;
if (vis[pxx][pyy][boxx][boxy])
continue;
vis[pxx][pyy][boxx][boxy] = 1;
auto weight = abs(ex - boxx) + abs(ey - boxy);
q.push({pxx, pyy, boxx, boxy, u.step + 1, weight});
}
}
return -1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
scanf("%s", graph[i]);
for (int j = 0; j < m; j++)
{
if (graph[i][j] == '0')
boxx = i, boxy = j, graph[i][j] = '.';
if (graph[i][j] == 'S')
px = i, py = j, graph[i][j] = '.';
if (graph[i][j] == 'E')
ex = i, ey = j, graph[i][j] = '.';
}
}
printf("%d\n", bfs());
system("pause");
return 0;
}
C++ 解法, 执行用时: 4ms, 内存消耗: 2172KB, 提交时间: 2020-10-26
#include <iostream>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <ctime>
using namespace std;
#define maxn 55
int n, m;
char board[maxn][maxn];
struct point {
int x;
int y;
point() : x(), y() {} // 无参构造函数
point(int a, int b) : x(a), y(b) {} // 有参构造函数
};
point start, expect, original;
bool visited[maxn][maxn][maxn][maxn];
struct Node {
int person_x, person_y, box_x, box_y, step, weight;
bool operator < (const Node& temp) const { // 重载，优先级
return temp.weight + abs(temp.person_x - temp.box_x) + abs(temp.person_y - temp.box_y) + temp.step
< weight + abs(person_x - box_x) + abs(person_y - box_y) + step;
}
};
Node tmp;
int direction[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
bool judge(int x, int y) {
if (x >= 1 && x <= n && y >= 1 && y <= m && board[x][y] != '#') {
return true;
}
return false;
}
int bfs() {
tmp = { start.x, start.y, original.x, original.y, 0, 0 };
priority_queue<Node> queue;
queue.push(tmp);
visited[start.x][start.y][original.x][original.y] = 1;
while (!queue.empty()) {
Node cur = queue.top();
//cout << cur.person_x << ", " << cur.person_y << endl;
queue.pop();
if (cur.box_x == expect.x && cur.box_y == expect.y) { // 箱子成功推到预期位置
return cur.step;
}
for (int i = 0; i < 4; i++) {
int person_x = cur.person_x + direction[i][0];
int person_y = cur.person_y + direction[i][1];
int box_x = cur.box_x;
int box_y = cur.box_y;
if (person_x == box_x && person_y == box_y) { // 碰到箱子就推箱子
box_x += direction[i][0];
box_y += direction[i][1];
}
if (!judge(person_x, person_y) || !judge(box_x, box_y)) {
continue;
}
if (visited[person_x][person_y][box_x][box_y] == 1) {
continue;
}
visited[person_x][person_y][box_x][box_y] = 1;
queue.push({person_x, person_y, box_x, box_y, cur.step + 1, abs(expect.x - box_x) + abs(expect.y - box_y)});
}
}
return -1;
}
int main() {
cin >> n >> m;
string str;
for (int i = 1; i <= n; i++) {
cin >> str;
for (int j = 1; j <= m; j++) {
board[i][j] = str[j - 1];
if (board[i][j] == 'S') {
start = { i, j };
}
else if (board[i][j] == '0') {
original = { i, j };
}
else if (board[i][j] == 'E') {
expect = { i, j };
}
}
}
cout << bfs() << endl;
system("pause");
return 0;
}