Untitled

 avatar
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