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 ; }