2 条题解

  • 1
    @ 2025-10-12 17:54:56
    #include<queue>
    #include<math.h>
    #include<stdio.h>
    #include<iostream>
    #include<vector>
    #include<iomanip>
    #include<string.h>
    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<utility>
    #include<cstring>
    #include<stack>
    #include<fstream>
    #include<string>
    using namespace std;
    typedef long long ll;
    const int N = 1e5 + 10;
    const int maxn = 5e2 + 10;
    const int INF = 0x3f3f3f3f;
    struct rec
    {
        int x , y , lie;
    };
    int n , m;
    char Map[maxn][maxn];
    int step[maxn][maxn][3];
    int dir[4][2] = { 0 , -1 , 0 , 1 , -1 , 0 , 1 , 0 };
    int next_x[3][4] = { { 0 , 0 , -2 , 1 } , { 0 , 0 , -1 , 1 } , { 0 , 0 , -1 , 2 } };
    int next_y[3][4] = { { -2 , 1 , 0 , 0 } , { -1 , 2 , 0 , 0 } , { -1 , 1 , 0 , 0 } };
    int next_lie[3][4] = { { 1, 1, 2 , 2 } , { 0 , 0 , 1 , 1 } , { 2 , 2 , 0 , 0 } }; 
    struct rec st , ed;
    bool valid( int x , int y )
    {
        if ( x <= 0 || x > n || y <= 0 || y > m )
    	{   
            return false;
        }
        return true;
    }
    void parse_st_ed()
    {
        for ( int i = 1 ; i <= n ; i++ )
    	{
            for ( int j = 1 ; j <= m ; j++ )
    		{
                if ( Map[i][j] == 'O' )
    			{
                    ed.x = i;
                    ed.y = j;
                    ed.lie = 0;
                    Map[i][j] = '.';
                }
                if ( Map[i][j] == 'X' )
    			{
                    for ( int k = 0 ; k < 4 ; k++ )
    				{
                        int dx = dir[k][0] + i;
                        int dy = dir[k][1] + j;
                        if ( valid( dx , dy ) && Map[dx][dy] == 'X' )
    					{
                            st.x = min( dx , i );
                            st.y = min( dy , j );
                            st.lie = k < 2 ? 1 : 2;
                            Map[i][j] = Map[dx][dy] = '.';
                            break;
                        }
                    }
                    if ( Map[i][j] == 'X' )
    				{
                        st.x = i;
                        st.y = j;
                        st.lie = 0;
                        Map[i][j] = '.';
                    }
                }
            }
        }
    }
    bool check( rec next )
    {
        if ( !valid( next.x , next.y ) )
    	{
            return false;
        }
        if ( Map[next.x][next.y] == '#' )
    	{
            return false;
        }
        if ( next.lie == 0 && Map[next.x][next.y] != '.' )
    	{
            return false;
        }
        if ( next.lie == 1 && Map[next.x][ next.y + 1 ] == '#' )
    	{
            return false;
        }
        if ( next.lie == 2 && Map[ next.x + 1 ][next.y] == '#' )
    	{
            return false;
        }
        return true;
    }
    int bfs()
    {
        for ( int i = 1 ; i <= n ; i++ )
    	{
            for ( int j = 1 ; j <= m ; j++ )
    		{
                for ( int k = 0 ; k < 3 ; k++ )
    			{
                    step[i][j][k] = -1;
                }
            }
        }
        queue<rec> q;
        step[st.x][st.y][st.lie] = 0;
        q.push(st);
        while ( !q.empty() )
    	{
            rec now = q.front();
            q.pop();
            for ( int i = 0 ; i < 4 ; i++ )
    		{
                rec next;
                next.x = now.x + next_x[now.lie][i];
                next.y = now.y + next_y[now.lie][i];
                next.lie = next_lie[now.lie][i];
                if ( check(next) && step[next.x][next.y][next.lie] == -1 )
    			{
                    step[next.x][next.y][next.lie] = step[now.x][now.y][now.lie] + 1;
                    q.push(next);
                    if ( next.x == ed.x && next.y == ed.y && next.lie == ed.lie )
    				{
                        return step[next.x][next.y][next.lie];
                    }
                }
            }
        }
        return -1;
    }
    int main()
    {
        while ( ~scanf( "%d %d" , &n , &m ) )
    	{
            if ( n == 0 && m == 0 )
    		{
                break;
            }
            for ( int i = 1 ; i <= n ; i++ )
    		{
                for ( int j = 1 ; j <= m ; j++ )
    			{
                    cin >> Map[i][j];
                }
            }
            parse_st_ed();
            int ans = bfs();
            if ( ans != -1 )
    		{
                printf( "%d\n" , ans );
            }
    		else
    		{
                printf( "Impossible\n" );
            }
        }
        return 0;
    }
    

    信息

    ID
    83
    时间
    1000ms
    内存
    128MiB
    难度
    1
    标签
    递交数
    73
    已通过
    51
    上传者