BFStaomangkc

#include<iostream> using namespace std; int quex[1000000], quey[1000000], visit[100][100]; int front, rear; int a[100][100]; int kq, n, m, T, ct, kl; int dx[100], dy[100], kc[100][100]; int dc[] = { 0, 1, -1, 0}; int ddc[] = {1, 0, 0, -1}; bool check(int x, int y) { if( x < 0 || x >= n || y < 0 || y >= m) return false; else return true; } void reset() { for(int i = 0; i < n; i++) for(int j = 0; j < m ; j++) { visit[i][j] = 0; } front = rear = 0; } int getDinh(int r,int c){ for(int i=1;r<ct;i++){ if(dx[i] == r && dy[i] == c){ return i; } } } void BFS(int x, int y , int dinh) { int tx, ty, nx, ny; reset(); quex[rear] = x; quey[rear] = y; rear ++; visit[x][y] = 1; kc[x][y] = 0; while( front != rear) { tx = quex[front]; ty = quey[front]; front ++; for(int move = 0; move < 4; move ++) { nx = tx + dc[move]; ny = ty + ddc[move]; if( check(nx,ny) && a[nx][ny] != 2 && visit[nx][ny] == 0) { quex[rear] = nx; quey[rear] = ny; rear ++; visit[nx][ny] = visit[tx][ty] + 1; if(a[nx][ny] == 1){ int d = getDinh(nx,ny); kc[dinh][d] = visit[nx][ny]-1; } } } } } int main() { freopen("input.txt","r",stdin); cin >> T; for(int tc = 1; tc <= T; tc ++) { int robotR,robotC; ct = 1; cin >> n >> m; for(int i = 0; i < n; i++) for(int j = 0; j< m; j++) { kc[i][j] = 0; cin >> a[i][j]; if( a[i][j] == 3 ) { robotR = i; robotC = j; } if( a[i][j] == 1 ) { dx[ct] = i; dy[ct] = j; ct++; } } BFS(robotR,robotC,0); for(int i = 1; i < ct; i++) { BFS(dx[i], dy[i],i); } for(int i = 0; i < ct; i++) { for(int j = 0; j< ct; j++) { cout << kc[i][j] <<" "; } cout << endl; } } }