1839. 恶魔之城

#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();
}

#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;
}

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

}