AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

洛谷 P1126. 机器人搬重物    原题链接    简单

作者: 作者的头像   偷月亮的喵 ,  2025-05-10 17:53:02 · 安徽 ,  所有人可见 ,  阅读 3


0


#include <bits/stdc++.h>
using namespace std;
const int N = 55;
//face= 0-西 1-东 2-北 3-南
const int dx[] = { 0,0,-1,1 };//face=0,1,2,3时的方向值,左右和上下
const int dy[] = { -1,1,0,0 };
const int turnLeft[] = { 3,2,0,1 };//face=0,1,2,3时
const int turnRight[] = { 2,3,1,0 };
struct node {
    int x, y, face;//位置 面对的方向
}st, en, now, nx;//起点 终点 当前点 下一点
int maze[N][N], vis[N][N][4];//迷宫地图,状态标记数组(位置和面对的方向)
int n, m, ans = -1;
void bfs() {
    queue<node> q;
    vis[st.x][st.y][st.face] = 0;
    q.push(st);
    while (!q.empty()) {
        now = q.front(), q.pop();
        if (now.x == en.x && now.y == en.y) {
            ans = vis[now.x][now.y][now.face];
            return;
        }
        nx = now;//准备直走
        for (int i = 1; i <= 3; i++) {//沿着当前方向走i步
            nx.x += dx[now.face], nx.y += dy[now.face];
            if (nx.x < 1 || nx.y < 1 || nx.x >= n || nx.y >= m || maze[nx.x][nx.y]) break;//此路不通
            if (vis[nx.x][nx.y][nx.face] != -1) continue;//该状态扩展过了
            //注意此处,边界处不可走(0~n行 0~m列)
            vis[nx.x][nx.y][nx.face] = vis[now.x][now.y][now.face] + 1;
            q.push(nx);
        }
        nx = now;//准备转换方向
        nx.face = turnLeft[now.face];//左转
        if (vis[nx.x][nx.y][nx.face] == -1) {
            vis[nx.x][nx.y][nx.face] = vis[now.x][now.y][now.face] + 1;
            q.push(nx);
        }
        nx.face = turnRight[now.face];//右转
        if (vis[nx.x][nx.y][nx.face] == -1) {
            vis[nx.x][nx.y][nx.face] = vis[now.x][now.y][now.face] + 1;
            q.push(nx);
        }

    }
}
int main() {
    memset(vis, -1, sizeof vis);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)//读入格子的值
        for (int j = 1; j <= m; j++) {
            int a;
            scanf("%d", &a);
            if (a) {//该格子为障碍(i,j视为格子右下角坐标),则障碍的四个点均不可走
                maze[i][j] = maze[i - 1][j - 1] = maze[i - 1][j] = maze[i][j - 1] = 1;
            }
        }
    scanf("%d%d%d%d %c", &st.x, &st.y, &en.x, &en.y, &st.face);
    st.face = (st.face == 'W' ? 0 : (st.face == 'E' ? 1 : (st.face == 'N' ? 2 : 3)));//w-0 E-1 N-2 S-3
    bfs();
    if (ans == -1) printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息