Untitled
unknown
plain_text
2 years ago
1.6 kB
7
Indexable
#include<iostream> using namespace std; int t,m,n; bool checkbien(int x, int y) { if (x<0 || x>m || y<0 || y>m) return false; return true; } char Map[500][500]; int D[400][400]; int dx[4] = {0,-1,0,1}; int dy[4] = {1,0,-1,0}; char Qx[100000], Qy[100000]; int Qd[100000]; int rear = -1; int front = -1; void push(int x, int y,int d) { rear ++; Qx[rear] = x; Qy[rear] = y; Qd[rear] = d; } void pop(int &x, int &y, int &d) { front ++; x = Qx[front]; y = Qy[front]; d = Qd[front]; } int BFS(int x, int y,int d) { push(x,y,0); while (rear != front) { pop(x,y,d); for (int i=0; i<4; i++) { int xx = x+dx[i]; int yy = y+dy[i]; if (checkbien(xx,yy)) { if (Map[xx][yy] == 'E') { push(xx,yy,d+1); Map[xx][yy] = 'S'; } else if (Map[xx][yy] == 'B') { push(xx,yy,d+2); Map[xx][yy] = 'S'; } else {if (Map[xx][yy] == 'T') { return d+1; } else return -1; } } } } } int main() { freopen("input.txt","r",stdin); cin >> t; int tx,ty; int yx,yy; for (int tc=1; tc<=t; tc++) { cin >> m >> n; front = rear = -1; for (int i=0; i<m; i++) cin >> Map[i]; for (int i=0; i<m; i++) { for (int j=0; j<n; j++) { if (Map[i][j] == 'Y') { yx = i; yy = j; } else if (Map[i][j] = 'T') { tx = i; ty = j; } } } cout << "#" << tc << " " << BFS(yx,yy,0) << endl; } return 0; }
Editor is loading...