BFS2

#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; 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 BFS(int x, int y, int xx, int yy) { 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 ++; if( tx == xx && ty == yy) { return kc[tx][ty]; } 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) { visit[nx][ny] = 1; kc[nx][ny] = kc[tx][ty] + 1; quex[rear] = nx; quey[rear] = ny; rear ++; } } } } int main() { freopen("input.txt","r",stdin); cin >> T; for(int tc = 1; tc <= T; tc ++) { ct = 0; cin >> n >> m; for(int i = 0; i < n; i++) for(int j = 0; j< m; j++) { kc[i][j] = -1; cin >> a[i][j]; if( a[i][j] == 3 ) { dx[ct] = i; dy[ct] = j; ct++; } if( a[i][j] == 1 ) { dx[ct] = i; dy[ct] = j; ct++; } } for(int i = 0; i < ct; i++) { cout <<"{" <<dx[i] <<","<<dy[i] <<"} "; } cout << endl; int r = BFS(1,1,3,5); cout << r << endl; } }