上代码

#include <bits/stdc++.h>
using namespace std;
int n, m, c1, c2, d, dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}, firstx, firsty;
int endx, endy;
string a[355][355], s;
bool l[355][355], shield[355][355];
int js( string k )
{
	int sum = 0;
	int cnt = k.size();
	while( cnt > 0 )
	{
		cnt --;
		sum = sum * 10 + k[cnt] - '0';
	}
	return sum;
}
struct node
{
    int x, y, sumc1, sumc2, sumtime, sum;
};
queue <node> Q;
void check( int startx, int starty, int num )
{
    for( int i = 0; i < 8; i ++ )
    {
        int xx = startx, yy = starty;
        while( xx >= 1 && yy >= 1 && xx <= n && yy <= m )
        {
        	// cout << xx << " " << yy << " ";
        	// cout << xx - startx + yy - starty << endl;
        	if( abs( xx - startx ) + abs( yy - starty ) >= num ) break;
            shield[xx][yy] = 1;
            xx += dx[i];
            yy += dy[i];
        }
    }
    return ;
}
bool b;
node bfs( )
{
    node mintarget = {0, 0, 999999, 999999, 999999, 999999};
    node z = {firstx, firsty, 0, 0, 0, 0};
    Q.push(z);
    while( !Q.empty() )
    {
        node now = Q.front();
        // cout << now.x << " " << now.y << endl;
        Q.pop();
        for( int i = 0; i < 8; i ++ )
        {
            node tmp = now;
            tmp.x += dx[i];
            tmp.y += dy[i];
            tmp.sumtime ++;
            int xn = tmp.x, yn = tmp.y;
            if( xn > n || yn > m || xn < 1 || yn < 1 || l[xn][yn] )
                continue;
            if( shield[xn][yn] ) continue;
            if( tmp.sumc1 > c1 || tmp.sumc2 > c2 ) continue;
            if( xn == endx && yn == endy )
            {
                if( tmp.sumtime < mintarget.sumtime )
                {
                    mintarget = tmp;
                    break;
                }
                if( tmp.sumtime == mintarget.sumtime )
                {
                    if( tmp.sum < mintarget.sum )
                    {
                        mintarget = tmp;
                        break;
                    }
                    if( tmp.sum == mintarget.sum )
                    {
                        if( tmp.sumc1 < mintarget.sumc1 )
                        {
                            mintarget = tmp;
                        }
                    }
                }
                b = 1;
            }
            Q.push(tmp);
            l[xn][yn] = 1;
        }
        int syx[4] = {0, 0, d, -d};
        int syy[4] = {d, -d, 0, 0};
        for( int i = 0; i < 4; i ++ )
        {
            node tmp = now;
            tmp.x += syx[i];
            tmp.y += syy[i];
            int xn = tmp.x, yn = tmp.y;
            if( xn > n || yn > m || xn < 1 || yn < 1 || l[xn][yn] )
                continue;
            if( shield[xn][yn] ) continue;
            if( tmp.sumc1 > c1 || tmp.sumc2 + 1 > c2 ) continue;
            tmp.sumtime ++;
            tmp.sumc2 ++;
            tmp.sum ++;
            if( xn == endx && yn == endy )
            {
                if( tmp.sumtime < mintarget.sumtime )
                {
                    mintarget = tmp;
                    break;
                }
                if( tmp.sumtime == mintarget.sumtime )
                {
                    if( tmp.sum < mintarget.sum )
                    {
                        mintarget = tmp;
                        break;
                    }
                    if( tmp.sum == mintarget.sum )
                    {
                        if( tmp.sumc1 < mintarget.sumc1 )
                        {
                            mintarget = tmp;
                        }
                    }
                }
                b = 1;
            }
            l[xn][yn] = 1;
            Q.push( tmp );
        }
        for( int i = 0; i < 8; i ++ )
        {
            node tmp = now;
            tmp.x += dx[i];
            tmp.y += dy[i];
            int xn = tmp.x, yn = tmp.y;
            if( xn > n || yn > m || xn < 1 || yn < 1 || l[xn][yn] )
                continue;
            if( tmp.sumc1 + 1 > c1 || tmp.sumc2 > c2 ) continue;
            if( a[xn][yn] == "#" ) continue;
            tmp.sumc1 ++;
            tmp.sum ++;
            if( xn == endx && yn == endy )
            {
                if( tmp.sumtime < mintarget.sumtime )
                {
                    mintarget = tmp;
                    break;
                }
                if( tmp.sumtime == mintarget.sumtime )
                {
                    if( tmp.sum < mintarget.sum )
                    {
                        mintarget = tmp;
                        break;
                    }
                    if( tmp.sum == mintarget.sum )
                    {
                        if( tmp.sumc1 < mintarget.sumc1 )
                        {
                            mintarget = tmp;
                        }
                    }
                }
                b = 1;
            }
            Q.push(tmp);
            l[xn][yn] = 1;
        }
        for( int i = 0; i < 4; i ++ )
        {
            node tmp = now;
            tmp.x += syx[i];
            tmp.y += syy[i];
            int xn = tmp.x, yn = tmp.y;
            if( xn > n || yn > m || xn < 1 || yn < 1 || l[xn][yn] )
                continue;
            if( a[xn][yn] == "#" ) continue;
            if( tmp.sumc1 + 1 > c1 || tmp.sumc2 + 1 > c2 ) continue;
            tmp.sumtime ++;
            tmp.sumc2 ++;
            tmp.sum += 2;
            tmp.sumc1 ++;
            if( xn == endx && yn == endy )
            {
            	// cout << xn << " " << yn << endl;
                if( tmp.sumtime < mintarget.sumtime )
                {
                    mintarget = tmp;
                    break;
                }
                if( tmp.sumtime == mintarget.sumtime )
                {
                    if( tmp.sum < mintarget.sum )
                    {
                        mintarget = tmp;
                        break;
                    }
                    if( tmp.sum == mintarget.sum )
                    {
                        if( tmp.sumc1 < mintarget.sumc1 )
                        {
                            mintarget = tmp;
                        }
                    }
                }
                b = 1;
            }
            l[xn][yn] = 1;
            Q.push( tmp );
        }
    }
    return mintarget;
}
int main()
{
    cin >> n >> m >> c1 >> c2 >> d;
    for( int i = 1; i <= n; i ++ )
    {
        for( int j = 1; j <= m; j ++ )
        {
            cin >> s;
            if( s != "." && s != "T" && s != "S" )
            {
                check( i, j, js(s) );
            }
            else if( s == "T" )
            {
                endx = i;
                endy = j;
            }
            else if( s == "S" )
            {
                firstx = i;
                firsty = j;
            }
            if( s != "." && s != "T" && s != "S" )
            {
                a[i][j] = "#";
            }
            else a[i][j] = s;
        }
    }
    // for( int i = 1; i <= n; i ++ )
    // {
    // 	for( int j = 1; j <= m; j ++ )
    // 	{
    // 		if( i == firstx && j == firsty )
    // 		{
    // 			cout << 'S' << " ";
    // 			continue;
    // 		}
    // 		if( i == endx && j == endy )
    // 		{
    // 			cout << "T" << " ";
    // 			continue;
    // 		}
    // 		cout << shield[i][j] << " ";
    // 	}
    // 	cout << endl;
    // }
    node u = bfs();
    if( b ) cout << u.sumtime << " " << u.sumc1 << " " << u.sumc2;
    else cout << -1;
}