BFS70分求助!!!
查看原帖
BFS70分求助!!!
677234
FstAutoMaton楼主2022/10/11 09:39

找不到错了

#include <bits/stdc++.h>
using namespace std;
#define int signed long long
char a[1205][1205];
int n, m, sum[1205][1205], dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1}, sx[4] = {2, -2, 0, 0};
int sy[4] = {0, 0, 2, -2}, fx[4] = {1, 1, -1, -1};
int fy[4] = {-1, 1, -1, 1};
bool l[1205][1205];
struct node
{
    int x, y;
};
void bfs()
{
    queue <node> Q;
    Q.push( {1, n} );
    Q.push( {n, 1} );
    Q.push( {1, 1} );
    sum[1][1] = 1;
    sum[1][n] = 1;
    sum[n][1] = 1;
    l[1][1] = 1;
    l[n][1] = 1;
    l[1][n] = 1;
    while( !Q.empty() )
    {
        node tmp = Q.front();
        Q.pop();
        if( tmp.x == n && tmp.y == n )
        {
            cout << sum[n][n];
            return ;
        }
        if( a[tmp.x][tmp.y] == 'A' )
        {
            for( int i = 0; i < 4; i ++ )
            {
                int xn = tmp.x + dx[i], yn = tmp.y + dy[i];
                if( xn > n || yn < 1 || xn < 1 || yn > n )
                    continue;
                if( l[xn][yn] || a[xn][yn] == '*' ) continue;
                Q.push( {xn, yn} );
                l[xn][yn] = 1;
                sum[xn][yn] = sum[tmp.x][tmp.y] + 1;
            }
        }
        else if( a[tmp.x][tmp.y] == 'B' )
        {
            for( int i = 0; i < 4; i ++ )
            {
                int xn = tmp.x + sx[i], yn = tmp.y + sy[i];
                if( xn > n || yn < 1 || xn < 1 || yn > n )
                    continue;
                if( l[xn][yn] || a[xn][yn] == '*' ) continue;
                Q.push( {xn, yn} );
                l[xn][yn] = 1;
                sum[xn][yn] = sum[tmp.x][tmp.y] + 1;
            }
        }
        else if( a[tmp.x][tmp.y] == 'C' )
        {
            for( int i = 0; i < 4; i ++ )
            {
                int xn = tmp.x + fx[i], yn = tmp.y + fy[i];
                if( xn > n || yn < 1 || xn < 1 || yn > n )
                    continue;
                if( l[xn][yn] || a[xn][yn] == '*' ) continue;
                Q.push( {xn, yn} );
                l[xn][yn] = 1;
                sum[xn][yn] = sum[tmp.x][tmp.y] + 2;
            }
        }
    }
    cout << "No answer";
}
signed main()
{
    cin >> n;
    for( int i = 1; i <= n; i ++ )
    {
        for( int j = 1; j <= n; j ++ ) 
        {
            cin >> a[i][j];
            sum[i][j] = 9999999;
        }
    }
    bfs();
}
2022/10/11 09:39
加载中...