Untitled
unknown
plain_text
2 years ago
1.4 kB
3
Indexable
#include<iostream> using namespace std; int n,m; int map[101][101]; int vs[101][101] = {0}; int Qx[10000000], Qy[1000000], Qd[10000000]; int front =-1, rear = -1; int dx[4] = {0,1,0,-1}; int dy[4] = {1,0,-1,0}; int start_x, start_y; int t; bool checkbien(int x, int y) { if ( x <0 || x >=m || y < 0 || y >=n) return false; return true; } 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) { int max = 0; int xx, yy; push(x,y,d); while (front != rear) { pop (x,y,d); for (int i=0; i<4; i++) { xx = x + dx[i]; yy = y + dy[i]; if (checkbien(xx,yy) && map[xx][yy] == 1 && vs[xx][yy] == 0) { push(xx,yy,d+1); vs[xx][yy] = d+1; if (max < vs[xx][yy]) max = vs[xx][yy]; } } } return max; } int main() { cin >> t; for (int tc =1; tc <= t; tc++){ cin >> n >> m; front = rear = -1; for (int i=0; i<m; i++) for (int j=0; j<n; j++) cin >> map[i][j]; for (int i=0; i<m; i++) for (int j=0; j<n; j++) vs[i][j] = 0; cin >> start_y >> start_x; vs[start_x-1][start_y-1] = 1; cout << Bfs(start_x-1,start_y-1,1)<<endl; } return 0; }
Editor is loading...