警示!自己一开始WA最后一个点
查看原帖
警示!自己一开始WA最后一个点
113001
xuhrrr楼主2024/1/21 12:14

本题我的思路和题解一相似,但是我一开始想的是用ans[][]的二维数组来储存每一步的答案,没通过最后一个测试用例。错误代码如下:

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
char map[305][305];
int ans[305][305],vis[305][305];
struct door{
    int x,y;
    int _x,_y;
};
struct node{
    int x,y;
};
queue<node>q;
door a[30]; //记录传送门的位置
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int main()
{
    memset(ans, 0 ,sizeof(ans));
    for(int i = 0 ; i <= 29 ; ++i){
        a[i].x = a[i].y = a[i]._x = a[i]._y = 0;
    }
    //初始化
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= m ; ++j){
            cin >> map[i][j];
            if(map[i][j] >= 'A' && map[i][j] <= 'Z'){
                int tmp = map[i][j] - 'A';
                if(a[tmp].x == 0 && a[tmp].y == 0){
                    a[tmp].x = i;
                    a[tmp].y = j;
                }
                else{
                    a[tmp]._x = i;
                    a[tmp]._y = j;
                }
            }
            if(map[i][j] == '@'){
                node tmp = {i,j};
                q.push(tmp);
                vis[i][j] = 1;
            }
            if(map[i][j] == '#'){
                vis[i][j] = 1;
            }
        }
    }
    //将传送门的位置记录
    while(!q.empty()){
        node tmp = q.front();
        q.pop();
        int ux = tmp.x;
        int uy = tmp.y;
        if(map[ux][uy] == '='){
            cout << ans[ux][uy] << endl;
            break;
        }
        if(map[ux][uy] >= 'A' && map[ux][uy] <= 'Z'){
            int temp = map[ux][uy] - 'A';
            if(a[temp].x == ux && a[temp].y == uy){
                ux = a[temp]._x;
                uy = a[temp]._y;
                ans[ux][uy] = ans[a[temp].x][a[temp].y];
            }
            else{
                ux = a[temp].x;
                uy = a[temp].y;
                ans[ux][uy] = ans[a[temp]._x][a[temp]._y];
            }
        }
        for(int k = 0 ; k < 4 ; ++k){
            int nx = ux + dir[k][0];
            int ny = uy + dir[k][1];
            if(nx <= 0 || nx > n || ny <= 0 || ny > m || vis[nx][ny] != 0){
                continue;
            }
            ans[nx][ny] = ans[ux][uy] + 1;
            vis[nx][ny] = 1;
            node newnode = {nx,ny};
            q.push(newnode);
        }
    }
    return 0;
}

我发现比较tricky的一个点就是这个传送门处的ans赋值有问题,由于最后一个点比较特殊相当于是隔了距离1使得可能出现重复赋值使得我的答案变的少了1。正确的想法应该是不要在这个点处多次赋值,直接用原来的传送门的t就行如~~~~~~果未来有人遇到同样的问题希望能得到一点帮助。~~ 肯定只有我这种蒟蒻遇到啦qaq

2024/1/21 12:14
加载中...