1839. 恶魔之城

Andrew-Malcom

include

#include<queue>
#include<string>
#include<algorithm>
#define FUCK ios::sync_with_stdio(false)
using namespace std;
int dx, dy, ex, ey;
int n, m;
struct Node {
    int i, j, dis;
    Node(int i, int j, int dis) :i(i), j(j), dis(dis) {}
};
struct Source {
    int x, y;
}sd[201][201];
char str[201][201];
void output(int x, int y)
{
    if (x != dx || y != dy) output(sd[x][y].x, sd[x][y].y);   
    printf("%d %d\n", x, y);
}
void bfs()
{
    queue<Node>Q; int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            cin >> str[i][j];
            if (str[i][j] == 'S') {
                dx = i, dy = j;
            }
            if (str[i][j] == 'E') {
                ex = i, ey = j;
            }
        }
    }
    Q.push(Node(dx, dy, 0));
    sd[dx][dy].x = dx;
    sd[dx][dy].y = dy;
    sd[ex][ey].x = ex;
    sd[ex][ey].y = ey;
    while (!Q.empty()) {
        Node x = Q.front();
        Q.pop();
        if (x.i == ex && x.j == ey) {
            cout << x.dis << endl;
            output(ex, ey);
            return;
        }
        else {
            if (str[x.i + 1][x.j] != '*'&&x.i+1<=n-1) {
                Q.push(Node(x.i + 1, x.j, x.dis + 1));
                str[x.i + 1][x.j] = '*';
                sd[x.i + 1][x.j].x = x.i;
                sd[x.i + 1][x.j].y = x.j;
            }
            if (str[x.i - 1][x.j] != '*'&&x.i-1>=0) {
                Q.push(Node(x.i - 1, x.j, x.dis + 1));
                str[x.i - 1][x.j] = '*';
                sd[x.i - 1][x.j].x = x.i;
                sd[x.i - 1][x.j].y = x.j;
            }
            if (str[x.i][x.j - 1] != '*'&&x.j-1>=0) {
                Q.push(Node(x.i, x.j - 1, x.dis + 1));
                str[x.i][x.j - 1] = '*';
                sd[x.i][x.j - 1].x = x.i;
                sd[x.i][x.j - 1].y = x.j;
            }
            if (str[x.i][x.j + 1] != '*'&&x.j+1<=m-1) {
                Q.push(Node(x.i, x.j + 1, x.dis + 1));
                str[x.i][x.j + 1] = '*';
                sd[x.i][x.j + 1].x = x.i;
                sd[x.i][x.j + 1].y = x.j;
            }
        }
    }
    cout << -1 << endl;
}
int main()
{
            FUCK;cin.tie(0);
            cin >> n >> m;
            cin.get();
        bfs();
}
solofandy_

本人菜鸟 望高人指点
建广义图 用优先队列 [em:01]

Money4
#include<bits/stdc++.h>
using namespace std;
char maze[200][200];
int m, n;
bool flag = false;
struct node
{
    int x;
    int y;
}last[200][200];  //标记上一个点位
vector<node> ans;
int start_x, start_y, end_x, end_y;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
void bfs() {
    queue<node> q;
    node p = { start_x, start_y };
    q.push(p);

    while (!q.empty()) {
        node cur = q.front();
        q.pop();
        if (cur.x == end_x && cur.y == end_y) {
            ans.emplace_back(cur);
            node l = last[end_x][end_y];
            while (l.x != start_x || l.y != start_y) {
                ans.emplace_back(l);
                l = last[l.x][l.y];
            }
            ans.emplace_back(l);
            printf("%d\n", ans.size() - 1);
            for (int a = ans.size() - 1; a >= 0; a--) {
                printf("%d %d\n", ans[a].x, ans[a].y);
            }
            flag = true;
            return;
        }
        else {
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + cur.x;
                int ny = dy[i] + cur.y;
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] != '*') {
                    node next = { nx,ny };
                    last[nx][ny] = cur;
                    maze[nx][ny] = '*';      //走过的标为"陷阱"
                    q.push(next);
                }
            }
        }
    }
}

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> maze[i][j];
            if (maze[i][j] == 'S') {
                start_x = i;
                start_y = j;
            }
            if (maze[i][j] == 'E') {
                end_x = i;
                end_y = j;
            }
        }
    }
    bfs();
    if (flag) return 0;
    else printf("-1\n");
    return 0;
}
我只想问还有谁

我摊牌了,我就是耗时之王;
import java.util.*;

public class Main{

static void print(Position p){//用递归的方法打印最短路径的节点
     if(p.parent==null){
      System.out.println((p.r-1)+" "+(p.c-1));//减一是因为矩阵是从11开始存储的
         return;
      }      
   print(p.parent);
  System.out.println((p.r-1)+" "+(p.c-1));

}



public static void main(String[] args) {
    char[][] matrix = new char[210][210];//存矩阵中每个位置的状态
    int[][] visited = new int[210][210];//bfs标记这个点是否被访问过
    Position start = new Position();
    Position goal = new Position();
    Direction[] d = new Direction[4];
    d[0] = new Direction(0, -1);
    d[1] = new Direction(0, 1);
    d[2] = new Direction(1, 0);
    d[3] = new Direction(-1, 0);

    Queue<Position> que = new LinkedList<Position>();
    int n, m;
    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    sc.nextLine();
    for (int i = 0; i < 210; i++) {//初始化矩阵让所有的点都为*’;
        for (int j = 0; j < 210; j++) {
            matrix[i][j] = '*';
        }
    }
    for (int i = 1; i <= n; i++) {//从1开始表明输入矩阵的四周都被*围了起来
        String s=sc.nextLine().trim();
        for (int j = 1; j <= m; j++) {
            matrix[i][j] = s.charAt(j-1);

            if (matrix[i][j] == 'S') {//起点
                start = new Position(i, j, 0,null);

            } else if (matrix[i][j] == 'E') {//终点
                goal = new Position(i, j, -1,null);
            }
            visited[i][j] = 0;
        }

    }

    que.add(start);//起点入队
    visited[start.r][start.c] = 1;//标记变为1
    Position ps = new Position();
    while (!que.isEmpty()) {//进行一次入队操作
        ps = que.peek();//取队首元素ps同时是此次循环入队的元素的父节点
        if (ps.r == goal.r && ps.c == goal.c) {
            break;//找到则跳出循环
        }
        que.poll();//删除队首元素
        int r = ps.r, c = ps.c;

        for (int i = 0; i < 4; i++) {
            int nextr = r + d[i].dr;
            int nextc = c + d[i].dc;
            if (matrix[nextr][nextc] == '*') {//撞墙则结束本次循环
                continue;
            }
            if (visited[nextr][nextc] == 0) {

                Position q = new Position(nextr, nextc, ps.steps +1, ps);
                que.add(q);//此元素的入队
                visited[nextr][nextc] = 1;
            }
        }           
    }
    if (que.isEmpty()) {//所有元素都出队后仍未找到goal
        System.out.println(-1);
    }
    else
        {System.out.println(ps.steps);
        print(ps);}
}

}
class Position {
int r, c;
int steps;
Position parent;
Position(int r, int c, int steps,Position parent){//定义四元组用于存节点信息
this.r = r;
this.c = c;
this.steps = steps;
this.parent=parent;
}
Position() {}
}
class Direction{//定义上下左右四个方向
int dr,dc;
Direction(int dr,int dc){
this.dr=dr;
this.dc=dc;

}

}

10142130260

右下角的坐标为(n-1,m-1).然后n行,每行m个字符
也被坑了。。。 “ 右下角的坐标为(n-1,m-1).然后n行,每行m个字符 ”
难道就没有人跟我一样觉得这句话前后有点矛盾么 = =
坐标理解应该是按照数学上,这样n-1为横坐标,表示有n ” 列” ,纵坐标表示有多少行。而不是数组中的理解。
还好,后面给了下补充,“.然后n行,每行m个字符” 。。坑 。。 = =

[em:15][em:13]

你当前正在回复 博客/题目
存在问题!