Untitled
unknown
plain_text
a year ago
3.1 kB
5
Indexable
#include <iostream> using namespace std; int tc, T, n, m, arr[2001][2001], visited[2001][2001], d; int check[100][100]; int save[100][100]; int kt[20]; int u, v, k, tx, ty; int frontX, frontY, rearX, rearY, qX[50000], qY[50000]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1}; int st = 0; int result = -1; int sum = 0; void initQueue() { frontX = rearX = frontY = rearY = -1; } int isEmptyX() { if (frontX == rearX) return 1; return 0; } int isEmptyY() { if (frontY == rearY) return 1; return 0; } void enQueueX(int elementX) { rearX++; qX[rearX] = elementX; } void enQueueY(int elementY) { rearY++; qY[rearY] = elementY; } int deQueueX() { frontX++; return qX[frontX]; } int deQueueY() { frontY++; return qY[frontY]; } void rscheck(){ for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++) { visited[i][j] = 0; } } void rs(){ for (int i = 0; i < 1001; i++) for (int j = 0; j < 1001; j++) { visited[i][j] = 0; } } int BFS(int x, int y) { initQueue(); enQueueX(x); enQueueY(y); int a = 0; int b = 0; while (!isEmptyX()) { u = deQueueX(); v = deQueueY(); b = arr[u][v]; for (k = 0; k < 4; k++) { tx = u + dx[k]; ty = v + dy[k]; if (tx >= 0 && tx < n && ty >= 0 && ty < m && visited[tx][ty] == 0 && arr[tx][ty] != 0) { a = arr[tx][ty]; if(k == 0 && (a == 1 || a== 2|| a == 5 || a == 6)&&(b == 1 || b == 2 || b== 4|| b==7)){ visited[tx][ty] = visited[u][v] + 1; if(visited[tx][ty] == st + 1){ initQueue(); break; } enQueueX(tx); enQueueY(ty); }else if( k == 1 && (a == 1|| a == 3 || a == 6 || a == 7 )&& (b == 1|| b == 3||b == 4 || b == 5)){ visited[tx][ty] = visited[u][v] + 1; if(visited[tx][ty] == st + 1){ initQueue(); break; } enQueueX(tx); enQueueY(ty); }else if(k == 2 && (a == 1|| a == 2 || a == 4 || a == 7 )&&(b == 1|| b == 2|| b == 5|| b==6)){ visited[tx][ty] = visited[u][v] + 1; if(visited[tx][ty] == st + 1){ initQueue(); break; } enQueueX(tx); enQueueY(ty); }else if(k == 3 && (a == 1|| a == 3 || a == 4 || a == 5 )&& (b == 1|| b== 3|| b==6 ||b ==7)){ visited[tx][ty] = visited[u][v] + 1; if(visited[tx][ty] == st + 1){ initQueue(); break; } enQueueX(tx); enQueueY(ty); } } } } return 0; } void minimum(){ } void ans(int tc) { int x,y; cin>>x>>y>>st; // rs(); visited[x][y] = 1; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++) { cin>>arr[i][j]; } } BFS(x,y); for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++) { if(visited[i][j] <= st && visited[i][j]> 0){ sum++; } } } cout<<"Case #"<<tc<<endl; cout<<sum<<endl;; rs(); result = -1; sum = 0; d = 0; } int main() { // freopen("input.txt", "r", stdin); cin >> T; for (tc = 0; tc < T; tc++) { cin >>n>>m; ans(tc+1); } return 0; }
Editor is loading...
Leave a Comment