Untitled
unknown
plain_text
6 months ago
3.0 kB
2
Indexable
Never
#include<iostream> using namespace std; int N, M, SR, SC; int aChay[400][2]; int aHo[400][2]; int aThoat[400][2]; int kimCuong[20][20]; int map[20][20]; int chay, ho, thoat; int ans; void print(int in){ if (in == 0){ cout << "map kim cuong" << endl; for (int i = 1; i <= N; i++){ for (int j = 1; j <= M; j++) { cout << kimCuong[i][j] << "\t"; } cout << endl; } } if (in == 1){ cout << "map buoc di" << endl; for (int i = 1; i <= N; i++){ for (int j = 1; j <= M; j++) { cout << map[i][j] << "\t"; } cout << endl; } } } // queue int qx[100000]; int qy[100000]; int front = -1; int rear = -1; bool isEmpty(){ return front == -1; } void push(int x, int y){ if (front == -1) front = 0; rear++; qx[rear] = x; qy[rear] = y; } void pop(){ if (front >= rear) front = rear = -1; else front++; } // bfs chay int dx[] = {0,0,1,-1}; int dy[] = {1,-1,0,0}; int visitChay[20][20]; void BFSchay(int x, int y){ front = rear = -1; push(x,y); visitChay[x][y] = 1; while(!isEmpty()){ int x1 = qx[front]; int y1 = qy[front]; pop(); for (int i = 0; i < 4; i++){ int x2 = x1 + dx[i]; int y2 = y1 + dy[i]; if (x2>=1 && x2<=N && y2>=1 && y2<=M && visitChay[x2][y2] > visitChay[x1][y1] && map[x2][y2]>=0){ // dijkstra if (visitChay[x2][y2] > visitChay[x1][y1] + 1){ visitChay[x2][y2] = visitChay[x1][y1] + 1; push(x2,y2); } } } } } void reset(){ //for (int i = 0; i < 300; i++){ // aChay[i][0] = aChay[i][1] = 0; // aHo[i][0] = aHo[i][1] = 0; // aThoat[i][0] = aThoat[i][1] = 0; //} for (int i = 1; i <= N; i++){ for (int j = 1; j <= M; j++) { //kimCuong[i][j] = 0; map[i][j] = 0; visitChay[i][j] = 1000000; } } } int main(){ freopen("input.txt", "r", stdin); int TC; cin >> TC; for (int tc = 1; tc <= TC; tc++){ /* input */ reset(); cin >> N >> M >> SR >> SC; cin >> chay; for (int i = 0; i < chay; i++){ int xchay, ychay; cin >> xchay >> ychay; aChay[i][0] = xchay; aChay[i][1] = ychay; map[xchay][ychay] = 1; } cin >> ho; for (int i = 0; i < ho; i++){ int xho, yho; cin >> xho >> yho; aHo[i][0] = xho; aHo[i][1] = yho; map[xho][yho] = -1; } cin >> thoat; for (int i = 0; i < thoat; i++){ int xthoat, ythoat; cin >> xthoat >> ythoat; aThoat[i][0] = xthoat; aThoat[i][1] = ythoat; } // map kim cuong for (int i = 1; i <= N; i++){ for (int j = 1; j <= M; j++) { cin >> kimCuong[i][j]; } } /* program */ // tinh thoi diem chay //for (int i = 0; i < chay; i++){ // cout << aChay[i][0] << " " << aChay[i][1] << endl; // BFSchay(aChay[i][0],aChay[i][1]); //} BFSchay(1,1); for (int i = 1; i <= N; i++){ for (int j = 1; j <= M; j++) { cout << visitChay[i][j] << "\t"; } cout << endl; } /* ouput */ cout << "Case #" << tc << endl; cout << ans << endl; } }