栈和队列的深度练习题

上学之路2

#include<bits/stdc++.h>
using namespace std;

int py[4][4]={{-1,0}, {1,0}, {0,-1}, {0,1}};  //设置上下左右偏移
char s[505][505];
struct node
{
	int x,y,cnt;
};

int n, m;
int x,y;  //起点的行和列
int main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
    	for(int j=1; j<=m; j++){
    		cin >> s[i][j];
    		if(s[i][j] == 'S') 
    		{
    			x=i,y=j;
    		}
    	}
    }

    queue<node> q;  //来存储能走到哪些地方
    node d;
    d.x = x;
    d.y = y;
    s[x][y] = 'X';
    d.cnt = 1;
    q.push(d);
    while(q.size()){
    	d = q.front();
    	q.pop();
    	for(int i=0; i<4; i++){
    		int tx=d.x + py[i][0];
    		int ty=d.y + py[i][1];
    		if(tx>=1 && tx<=n && ty>=1 && ty<=m && s[tx][ty] !='X'){
    			if(s[tx][ty]=='T'){
    				cout << d.cnt + 1;
    				return 0;
    			}
    			int tcnt = d.cnt + 1;
    			node d1;
    			d1.x = tx;
    			d1.y = ty;
    			d1.cnt = tcnt;
    			s[tx][ty] = 'X';
    			q.push(d1);
    		}
    	}
    }
    cout << -1;

    return 0;
}