Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.1 kB
2
Indexable
Never
#include<iostream>

using namespace std;

int M, N;

int arr[301][301];

int visited[301][301];

int Q[9000000];

int cntMin = 10000;

int front, rear;

int dx[4] = {0, -1, 0, 1};

int dy[4] = {-1, 0, 1, 0};

enum map{

YOU,

EMPTY,

BRICK,

TARGET,

STEEL,

RIVER

};

void bfs(int row, int col){

front = rear = 0;

Q[rear++] = row;

Q[rear++] = col;

visited[row][col] = arr[row][col];

while(front != rear){

int r = Q[front++];

int c = Q[front++];

for (int i = 0; i < 4; i++)

{

int x = r + dx[i];

int y = c + dy[i];

if(x < 0 || x == M || y < 0 || y == N || arr[x][y] == STEEL || arr[x][y] == RIVER){

continue;

}

else{

if(visited[x][y] != 100000){

if(visited[r][c]+arr[x][y] < visited[x][y]){

Q[rear++] = x;

Q[rear++] = y;

visited[x][y] = visited[r][c]+arr[x][y];

}

}

else{

Q[rear++] = x;

Q[rear++] = y;

visited[x][y] = visited[r][c]+arr[x][y];

}

}

if(arr[x][y] == TARGET){

if(cntMin > visited[x][y]-arr[x][y]+1){

cntMin = visited[x][y]-arr[x][y]+1;

}

//cntMin = cnt + 1;

//return;

}

}

}

if(cntMin == 10000){

cntMin = -1;

}

}

int main(int argc, char** argv)

{

int test_case;

int T;

char c;

freopen("input.txt", "r", stdin);

cin >> T;

for(test_case = 1; test_case <= T; ++test_case)

{

cin >> M >> N;

int xStart, yStart;

for (int row = 0; row < M; row++)

{

for (int col = 0; col < N; col++)

{

cin >> c;

if(c == 'Y'){

arr[row][col] = YOU;

xStart = row;

yStart = col;

}

else if(c == 'T'){

arr[row][col] = TARGET;

}

else if(c == 'S'){

arr[row][col] = STEEL;

}

else if(c == 'B'){

arr[row][col] = BRICK;

}

else if(c == 'R'){

arr[row][col] = RIVER;

}

else if(c == 'E'){

arr[row][col] = EMPTY;

}

visited[row][col] = 100000;

}

}

cntMin = 10000;

bfs(xStart, yStart);

cout << "Case #" << test_case << endl << cntMin << endl;

//cout << "#" << test_case << " " << << endl;

}

return 0;

}