P1825 [USACO11OPEN]Corn Maze S

怀疑人生的题。。。。。bfs理解不够，我怀疑我会不会写bfs
问题：

1. 是否能使用level数组来标记步数？在将level数组改成结构体绑定步数之后AC
2. bfs出口语句if(g[x][y] == '=') return 步数 这句话放在哪到底有没有影响，我在将这句话从上面改到下面后AC
3. 传送门转移为什么不可以这样操作？（弹出队首元素，检查它的四连通域，如果存在传送门，那么直接把传送到的地点入队），而是要这样操作？（弹出队首元素检查他是不是传送门，如果是，那么把它改成传送到的位置的坐标，在遍历它的四连通域，取入队一些元素）
4. 关于是标记传送门传到的位置， 还是标记传送门的位置而不标记传送门的位置，还是两个都标记的问题。

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int N = 310, M = 90010;

struct Node{
    int x, y, w;
};

char g[N][N];
int st[N][N];
int p[M], t[26];
int n, m;
int a, b;
queue<Node> q;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int bfs(){
    q.push({a, b, 0});
    st[a][b] = 1;
    
    while(q.size()){
        auto h = q.front();
        q.pop();
        
        int x = h.x, y = h.y, w = h.w;
        
        if(isalpha(g[x][y]) && ~p[x * m + y]){
        	int t = p[x * m + y];
        	x = t / m;
        	y = t % m;
	}
        
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];
            if(g[a][b] == '#' || st[a][b]) continue;
            st[a][b] = 1;
            q.push({a, b, w + 1});
            if(g[a][b] == '=') return w + 1;
        }
    }
    
    return -1;
}

int main(){
    cin >> n >> m;
    
    memset(t ,-1, sizeof t);
    memset(p, -1, sizeof p);
    
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++){
            cin >> g[i][j];
            if(g[i][j] == '@') a = i, b = j;
            if(g[i][j] >= 'A' && g[i][j] <= 'Z'){
                if(t[g[i][j] - 'A'] == -1)
                    t[g[i][j] - 'A'] = i * m + j;
                else{
                    int a = t[g[i][j] - 'A'];
                    int b = i * m + j;
                    p[a] = b;
                    p[b] = a;
                }
            }
        }
        
    cout << bfs() << endl;
    
    return 0;
}

用level数组的错误代码

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int N = 310, M = 90010;

#define PII pair<int, int>
#define x first
#define y second

int level[N][N];
char g[N][N];
int st[N][N];
int p[M], t[26];
int n, m;
int a, b;
queue<PII> q;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int bfs(){
    q.push({a, b});
    st[a][b] = 1;
    
    while(q.size()){
        auto h = q.front();
        q.pop();
        
        int x = h.x, y = h.y;
        if(g[x][y] == '=') return level[x][y];
        
        if(isalpha(g[x][y]) && ~p[x * m + y]){
        	int t = p[x * m + y];
        	x = t / m;
        	y = t % m;
        	
        	level[x][y] = level[h.x][h.y];
	}
        
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];
            if(g[a][b] == '#' || st[a][b]) continue;
            st[a][b] = 1;
            level[a][b] = level[x][y] + 1;
            q.push({a, b});
        }
    }
    
    return -1;
}

int main(){
    cin >> n >> m;
    
    memset(t ,-1, sizeof t);
    memset(p, -1, sizeof p);
    
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++){
            cin >> g[i][j];
            if(g[i][j] == '@') a = i, b = j;
            if(g[i][j] >= 'A' && g[i][j] <= 'Z'){
                if(t[g[i][j] - 'A'] == -1)
                    t[g[i][j] - 'A'] = i * m + j;
                else{
                    int a = t[g[i][j] - 'A'];
                    int b = i * m + j;
                    p[a] = b;
                    p[b] = a;
                }
            }
        }
        
    cout << bfs() << endl;
    
    return 0;
}