Untitled

 avatar
unknown
plain_text
a year ago
1.9 kB
14
Indexable
#include<iostream>
using namespace std;

int T, N, M, arr[100][100], visited[100][100];
int Answer, startX, startY, endX, endY;

int dxr[4] = { 0, 0};
int dyr[4] = { 1, -1};
int dxc[2] = {1, -1};
int dyc[2] = {0, 0};

const int MAX = 10000;
struct Queue{
	int rear, front;
	int queue[MAX];
	Queue(){
		front = rear = -1;
	}

	void push(int value){
		queue[++rear] = value;
	}

	int pop(){
		return queue[++front];
	}
	bool isEmpty(){
		return front == rear;
	}
};

bool isValid(int x, int y){
	return x >= 0 && x < N && y >= 0 && y < M;
}

void bfs(int x, int y, int dist){
	Queue q;
	q.push(x);
	q.push(y);
	q.push(dist);

	while(!q.isEmpty()){
		int r = q.pop();
		int c = q.pop();
		int ndist = q.pop();

		if(arr[r][c] == 3){
			//cout << ndist << " ";
			if(Answer > ndist){
				Answer = ndist;
			}
		}
		// duyet hang ngang
		for(int i = 0; i < 2; i++){
			int nx = r + dxr[i];
			int ny = c + dxr[i];
			
			if(isValid(nx, ny) && arr[nx][ny] == 1 && visited[nx][ny] == 0){
				visited[nx][ny] = 1;
				q.push(nx);
				q.push(ny);
				q.push(ndist);
			}
		}
		// duyet hang doc
		for(int i = 0; i < 2; i++){
			for(int k = 1; k <= N && k < Answer; k++){
				int nx = r + k * dxc[i];
				int ny = c + k * dyc[i];
				
				if(isValid(nx, ny) && arr[nx][ny] == 1 && visited[nx][ny] == 0){
					if(ndist < k) {
						ndist = k;
					}
					visited[nx][ny] = 1;
					q.push(nx);
					q.push(ny);
					q.push(ndist);
					break;
				}
			}
		}
	}
}

int main(){
	freopen("Mario.txt", "r", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		Answer = 999;
		cin >> N >> M;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				cin >> arr[i][j];
				if(arr[i][j] == 2){
					startX = i;
					startY = j;
				}
			}
		}
		bfs(startX, startY, 1);
		cout << "Case #" << tc << endl;
		cout << Answer << endl;
	}
	return 0;
}
Editor is loading...
Leave a Comment