Rock Climbing

user_1164828
c_cpp
19 days ago
4.1 kB
3
Indexable
Never
```#include<iostream>
using namespace std;

int N, M;
int map[55][55];
int xS,yS, xE,yE;
int visited[55][55];
int queue[100000][2];
int l,r;
int dx[] ={-1,0,1,0};
int dy[] ={0,1,0,-1};
//So buoc nhay toi thieu
int h;

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

bool BFS(int row, int col){
//Reset visited[][]
for(int i=0;i<=N;i++){
for(int j=0;j<=M;j++){
visited[i][j]=0;
}
}
//Reset Queue
l=r=0;
//Them vao Queue
queue[r][0] = row;
queue[r++][1] = col;
//Danh dau la da tham
visited[row][col]=1;
//Duyet cho den khi queue rong
while(l!=r){
int x = queue[l][0];
int y = queue[l++][1];
//Neu den dich roi -> tra v true
if(map[x][y]==3)
return true;
//loang 1 huong
if(xE==N-1){
//cout << "hhehe";
for(int i=0;i<M;i++){
int ny = y + i;
if(map[xE][ny]==0)
break;
if(check(xE,ny) && visited[xE][ny]==0 && map[xE][ny]!=0){
if(map[xE][ny]==3){
//h=0;
return true;
}
}
}
}
//loang 4 huong
for(int i=0;i<4;i++){
if(i%2==0){
for(int j=0;j<=h;j++){
int nx = x + j*dx[i];
int ny = y + dy[i];
//Check bien && da tham chua && co duong di khong
if(check(nx,ny) && visited[nx][ny]==0 && map[nx][ny]!=0){
//Danh dau la da tham
visited[nx][ny] =1;
//push vao queue
queue[r][0] = nx;
queue[r++][1] =ny;
//Neu gap dich -> return
if(map[nx][ny]==3)
return true;
//Nho break vong for h ra
break;
}
}
}
else{
int nx = x + dx[i];
int ny = y + dy[i];
//Check bien && da tham chua && co duong di khong
if(check(nx,ny) && visited[nx][ny]==0 && map[nx][ny]!=0){
//Danh dau la da tham
visited[nx][ny] =1;
//push vao queue
queue[r][0] = nx;
queue[r++][1] =ny;
//Neu gap dich -> return
if(map[nx][ny]==3)
return true;
}
}
}
}
return false;
}

int main(){
// freopen("Text.txt","r",stdin);
//  int T;
//  cin >> T;
//  for(int t=1; t <= T; t++){
cin >> N >> M;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin >> map[i][j];
if(map[i][j]==3){
xE = i;
yE = j;
}
}
}
for(h=0;h<M;h++){
if(BFS(N,0))
break;
}
// cout << "Case #" << t << endl;
cout << h << endl;
// }
return 0;
}

//testcase//
5 8
1 1 1 1 0 0 0 0
0 0 0 3 0 1 1 1
1 1 1 0 0 1 0 0
0 0 0 0 0 0 1 0
1 1 1 1 1 1 1 1
5 5
1 1 1 1 3
0 0 1 1 0
1 1 1 0 0
0 0 0 0 0
1 0 0 0 0
5 5
1 1 1 1 1
0 0 0 0 3
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
5 5
1 1 1 1 3
1 1 1 1 0
0 0 0 0 0
1 1 1 0 0
1 0 0 0 0
8 8
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 3
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1
4 4
0 0 0 3
0 1 1 1
0 0 0 0
1 1 0 0
2 2
1 3
1 0
2 2
1 3
1 0
3 3
1 0 0
1 1 1
1 1 3
5 5
1 1 1 1 1
1 1 1 1 1
3 1 1 1 1
0 0 0 0 1
1 1 1 1 1
2 2
1 1
3 1
5 5
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 3
//
case 1: 2
case 2: 2
case 3: 3
case 4: 2
case 5: 5
case 6: 2
case 7: 1
case 8: 1
case 9: 0
case 10: 1
case 11: 0
case 12: 4```