Untitled

mail@pastecode.io avatar
unknown
plain_text
6 months ago
1.9 kB
1
Indexable
Never
#include<iostream>
using namespace std;
int n, m, visited[50][50];
int a[50][50];
int startx, starty, endx, endy;
int jump, jumpmin;
void backtrack(int row, int col, int state){
	if(jump>jumpmin) return;
	if(row==endx && col == endy){
		if(jump<jumpmin) jumpmin = jump;
		return;
	}
	for(int i=0; i<2; i++){
		if(i==0){
			for(int j=0; j<2; j++){
				if(j==0){
					for(int k=row; k<n; k++){
						if(visited[k][col]==0 && (a[k][col]==1||a[k][col]==3)){
							visited[k][col] = 1;
							jump+=1;
							backtrack(k, col, 0);
							visited[k][col]=0;
							jump-=1;
						}
						
					}
					
				}
				else{
					for(int k=row;k>=0 ; k--){
						if(visited[k][col]==0 && (a[k][col]==1||a[k][row]==3)){
							visited[k][col] = 1;
							jump+=1;
							backtrack(k, col, 0);
							visited[k][col]=0;
							jump-=1;
						}
					}
				}
			}
		}
		else if(i==1 && state==0){
			for(int j=0; j<2; j++){
				if(j==0){
					for(int k=col; k<m; k++){
						if(visited[row][k]==0 && (a[row][k]==1||a[row][k]==3)){
							visited[row][k] = 1;
							backtrack(row, k, 1);
							visited[row][k]=0;
						}
						
					}
				}
				else{
					for(int k=col-1;k>=0 ; k--){
						if(visited[row][k]==0 && (a[row][k]==1||a[row][k]==3)){
							visited[row][k] = 1;
							backtrack(row, k, 1);
							visited[row][k]=0;
						}
					}
						
				}
			}
		}
	}
}
int main(){
	int t;
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cin>>n>>m;
		for(int i=0; i<n; i++){
			for(int j=0;j<m; j++){
				cin>>a[i][j];
				visited[i][j] = 0;
				if(a[i][j]==2){
					startx = i;
					starty = j;
				}
				else if(a[i][j]==3){
					endx = i;
					endy = j;
				}
			}
		}
		jump = 0;
		jumpmin = 1000;
		visited[startx][starty]=1;
		backtrack(startx, starty,0);
		cout<<jumpmin<<endl;
		
	}
}
Leave a Comment