80分求助 有两个点WA
查看原帖
80分求助 有两个点WA
406437
保护我方三四楼主2021/3/3 22:49
#include<bits/stdc++.h>
using namespace std;
int n, m, sx, sy, fx, fy;
char sd;
int step[55][55];
bool vis[55][55];
int arr[55][55];
int dx[] = { 0,0,0,0,0,0,-1,-2,-3,1,2,3 };
int dy[] = { 1,2,3,-1,-2,-3,0,0,0,0,0,0 };

bool inmap(int x, int y){
    return x >= 1 && x <= n - 1 && y >= 1 && y <= m - 1 && !arr[x][y] && !arr[x + 1][y + 1] && !arr[x + 1][y] && !arr[x][y + 1];
}
struct node{
    int x, y;
    char d;
};
queue<node> q;
void bfs(int x, int y, char d){
    vis[x][y] = 1;
    step[x][y] = 0;
    q.push({x,y,d});
    while(!q.empty()){
        node b = q.front();
        if(b.d == 'W'){
            for(int i = 0; i < 3; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 1)){
                    step[nx][ny] = step[b.x][b.y] + 1;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'W'});
                } 
            }
            for(int i = 3; i < 6; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 3)){
                    step[nx][ny] = step[b.x][b.y] + 3;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'E'});
                } 
            }
            for(int i = 6; i < 9; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 2)){
                    step[nx][ny] = step[b.x][b.y] + 2;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'N'});
                } 
            }
            for(int i = 9; i < 12; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 2)){
                    step[nx][ny] = step[b.x][b.y] + 2;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'S'});
                } 
            }
        }
        if(b.d == 'E'){
            for(int i = 0; i < 3; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 3)){
                    step[nx][ny] = step[b.x][b.y] + 3;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'W'});
                } 
            }
            for(int i = 3; i < 6; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 1)){
                    step[nx][ny] = step[b.x][b.y] + 1;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'E'});
                } 
            }
            for(int i = 6; i < 9; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 2)){
                    step[nx][ny] = step[b.x][b.y] + 2;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'N'});
                } 
            }
            for(int i = 9; i < 12; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 2)){
                    step[nx][ny] = step[b.x][b.y] + 2;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'S'});
                } 
            }
        }
        if(b.d == 'N'){
            for(int i = 0; i < 3; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 2)){
                    step[nx][ny] = step[b.x][b.y] + 2;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'W'});
                } 
            }
            for(int i = 3; i < 6; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 2)){
                    step[nx][ny] = step[b.x][b.y] + 2;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'E'});
                } 
            }
            for(int i = 6; i < 9; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 1)){
                    step[nx][ny] = step[b.x][b.y] + 1;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'N'});
                } 
            }
            for(int i = 9; i < 12; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 3)){
                    step[nx][ny] = step[b.x][b.y] + 3;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'S'});
                } 
            }
        }
        if(b.d == 'S'){
            for(int i = 0; i < 3; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 2)){
                    step[nx][ny] = step[b.x][b.y] + 2;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'W'});
                } 
            }
            for(int i = 3; i < 6; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 2)){
                    step[nx][ny] = step[b.x][b.y] + 2;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'E'});
                } 
            }
            for(int i = 6; i < 9; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 3)){
                    step[nx][ny] = step[b.x][b.y] + 3;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'N'});
                } 
            }
            for(int i = 9; i < 12; i ++){
                int nx = b.x + dx[i], ny = b.y + dy[i];
                if(!inmap(nx,ny)) break;
                if(inmap(nx, ny) &&(!vis[nx][ny] || step[nx][ny] > step[b.x][b.y] + 1)){
                    step[nx][ny] = step[b.x][b.y] + 1;
                    vis[nx][ny] = 1;
                    q.push({nx,ny,'S'});
                } 
            }
        }
        q.pop();
    }
    return;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            cin >> arr[i][j];
        }
    }
    cin >> sx >> sy >> fx >> fy >> sd;
    bfs(sx, sy, sd);
    for(int i = 1; i <= n - 1; i ++){
        for(int j = 1; j <= m - 1; j ++){
            cout << setw(3) << step[i][j];
        }
        cout << endl;
    }
    if(vis[fx][fy]) cout << step[fx][fy];
    else cout << -1;
}
2021/3/3 22:49
加载中...