Untitled
plain_text
a month ago
2.0 kB
0
Indexable
Never
#include <iostream> using namespace std; int n, m; int data[3001][3001]; int visit[3001][3001]; int front, rear; int dx[] = {0, 0, -1, 1}; int dy[] = {-1, 1, 0, 0}; int sl, c1, c2; struct toado{ int x, y; }; toado queu[1000000]; void init() { rear = 0; front = 0; } void push(int xx, int yy) { queu[rear].x = xx; queu[rear].y = yy; rear ++; } toado pop() { toado td = queu[front]; front ++; return td; } void BFSN(int x, int y) { init(); int giatri = 1; push(x,y); visit[x][y] = giatri; int huong = 0; while (front < rear) { toado vitri = pop(); for (int i = 0; i < 2; i++) { giatri = 0; int xn = vitri.x +dx[i]; int yn = vitri.y +dy[i]; if (xn >= 0 && xn < n && yn >= 0 && yn < n && data[xn][yn] == 0 && visit[xn][yn] == 0 ) { push(xn,yn); visit[xn][yn] = visit[vitri.x][vitri.y]+giatri; } } } } void BFSD(int x, int y) { init(); int giatri = 1; push(x,y); visit[x][y] = giatri; int huong = 0; while (front < rear) { toado vitri = pop(); for (int i = 2; i < 4; i++) { giatri = 0; int xn = vitri.x +dx[i]; int yn = vitri.y +dy[i]; if (xn >= 0 && xn < n && yn >= 0 && yn < n && data[xn][yn] == 0 && visit[xn][yn] == 0 ) { push(xn,yn); visit[xn][yn] = visit[vitri.x][vitri.y]+giatri; } } } } int main() { freopen("input.txt", "r", stdin); cin >> sl; for (int stt = 1; stt <= sl; stt++) { n =0;m=0; cin >> n >> m; int vtdx =0, vtdy=0, vtcx=0, vtcy=0; cin >> vtdy >> vtdx >> vtcy >> vtcx; char kitu; for (int i = 1; i <= n; i++) { for (int j = 1; j <=m; j++) { cin >> kitu; data[i][j] = kitu - 48; visit[i][j] = 0; } } BFSN(vtdx,vtdy); for (int j = 0; j < m; j++) { BFSD(vtdx,j); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cout <<visit[i][j] <<" "; } cout <<endl; } cout << "Case #"<<stt<<endl; } return 0; }