bfs+分类讨论

（写得比较蠢，应该整一个bfs的函数会简便一点）
主要分两种大情况，一是不用钥匙开门就能走到终点，二是要找到钥匙开门才能走到终点。
在第一种情况中又有一种小情况，使用钥匙和不使用钥匙都能到达终点时，哪一种路径更短？
在第二种情况中，如果能找到钥匙，但从钥匙处出发走不到终点怎么办？如果找不到钥匙，但从钥匙处出发可以找到终点怎么办？需要仔细思考。

s1是不用钥匙时走到终点的最短路程。
s2是走到钥匙处的最短路程。
s3是从钥匙处走到终点的最短路程。

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
#define debug(x); for( int i = 1 ; i <= n ; i ++)        for( int k = 1 ; k <= m ; k ++)            if(k!=m)cout<<x[i][k]<<" ";        else cout<<x[i][k]<<"\n";
struct point{
    long long a ;
    long long b ;
};

char mapn[ 505 ][ 505 ];
long long sum1[ 505 ][ 505 ];
long long sum2[ 505 ][ 505 ];
long long sum3[ 505 ][ 505 ];
int x[ 4 ] = { 1 , -1 , 0 , 0 };
int y[ 4 ] = { 0 , 0 , 1 , -1 };
long long n , m , sk , ske , s1 , s2 , s3;
long long sx , sy , kx , ky , ex , ey ;
queue< point >q1;
queue< point >q2;
queue< point >q3;
bool inmap( int a , int b )
{
    if( a > n || a < 1 ) return 0 ;
    if( b > m || b < 1 ) return 0 ;
    return 1 ;
}
int main()
{
    cin >> n >> m ;
    n  ;
    m  ;
    memset( sum1 , -1 , sizeof sum1 );
    memset( sum2 , -1 , sizeof sum2 );
    memset( sum3 , -1 , sizeof sum3 );
    for( int i = 1 ; i <= n ; i ++)
        for( int k = 1 ; k <= m ; k ++)
            {
                cin >> mapn[ i ][ k ];
                if( mapn[ i ][ k ] == 'S') sx = i , sy = k ;
                if( mapn[ i ][ k ] == 'K') kx = i , ky = k ;
                if( mapn[ i ][ k ] == 'E') ex = i , ey = k ;
            }
    sum1[ sx ][ sy ] = 0 ;
    q1.push( { sx , sy } );
    while( !q1.empty() )
    {
        point temp = q1.front();
        q1.pop() ;
        for(int i = 0 ; i < 4 ; i ++ )
        {
            int tx = temp.a + x[ i ] ;
            int ty = temp.b + y[ i ] ;
            if( inmap( tx , ty ) && sum1[ tx ][ ty ] == -1 && mapn[ tx ][ ty ] != 'W' && mapn[ tx ][ ty ] != 'D')
            {
                sum1[ tx ][ ty ] = sum1[ temp.a ][ temp.b ] + 1 ;
                if( tx == ex && ty == ey )
                        {
                            s1 = sum1[ tx ][ ty ] ;
                            goto jump1 ;
                            }
                q1.push({ tx , ty });
            }
        }
    }

    jump1:
    if( sum1[ ex ][ ey ] == -1 ) s1 = 0 ;
    else s1 = sum1[ ex ][ ey ];

    sum2[ sx ][ sy ] = 0 ;
    q2.push({ sx , sy });
    while( !q2.empty() )
        {
            point temp = q2.front() ;
            q2.pop() ;
            for(int i = 0 ; i < 4 ; i ++)
            {
                int tx = temp.a + x[ i ] ;
                int ty = temp.b + y[ i ] ;
                if(  inmap( tx , ty ) && sum2[ tx ][ ty ] == -1 && mapn[ tx ][ ty ] != 'W' && mapn[ tx ][ ty ] != 'D' )
                    {
                        sum2[ tx ][ ty ] = sum2[ temp.a ][ temp.b ] + 1 ;
                        if( tx == kx && ty == ky )
                        {
                            s2 = sum2[ tx ][ ty ];
                            goto jump2 ;
                            }
                        q2.push({ tx , ty });
                    }
            }

        }

        jump2:
            if( sum2[ kx ][ ky ] == -1 )
                s2 = 0 ;
    //debug(sum2);
    sum3[ kx ][ ky ] = 0 ;
    q3.push( { kx , ky } );
    while( !q3.empty() )
    {
        point temp = q3.front();
        q3.pop() ;
        for(int i = 0 ; i < 4 ; i ++ )
        {
            int tx = temp.a + x[ i ] ;
            int ty = temp.b + y[ i ] ;
            if( inmap( tx , ty ) && sum3[ tx ][ ty ] == -1 && mapn[ tx ][ ty ] != 'W')
            {
                sum3[ tx ][ ty ] = sum3[ temp.a ][ temp.b ] + 1 ;
                if( tx == ex && ty == ey )
                        {
                            s3 = sum3[ tx ][ ty ] ;
                            goto jump3 ;
                            }
                q3.push({ tx , ty });
            }
        }
    }
    jump3:
        if( sum3[ ex ][ ey ] == -1)s3 = 0 ;

        //cout <<s1 << " "<<s2<<" "<<s3 ;

        if( s1 != 0 && s2 != 0 && s3 != 0)
            cout << min( s1 , s2 + s3 );
        else if( s1 == 0 && s2 != 0 && s3 != 0)
            cout << s2 + s3 ;
        else if( s1 != 0 && s2 != 0 && s3 == 0)
            cout << s1 ;
        else if( s1 != 0 && s2 == 0 )
            cout << s1 ;
        else if( s1 == 0 && s2 != 0 && s3 == 0)
        {
            cout << -1 ;
        }
        else if( s1 == 0 && s2 == 0)
        {
            cout << -1 ;
        }
        return 0 ;
}