Oriental Boyi OJ [Basic] Pawn Traversal

Title Description

On an n*m board (e.g., 6 rows and 7 columns) there is a pawn in the upper leftmost corner at the position (1,1). The pawn can only move down or to the right, and the pawn adopts the strategy of moving down first and then to the right when the next move reaches the head. Ask what moves can be made from the point (1,1) to the point (n,m), and output these moves.

importation

Two integers n, m represent the size of the board (3≤n≤8,3≤m≤8)

exports

Pawn Walking Route

example

importation

3 3

exports

1:1,1->2,1->3,1->3,2->3,3





2:1,1->2,1->2,2->3,2->3,3





3:1,1->2,1->2,2->2,3->3,3





4:1,1->1,2->2,2->3,2->3,3





5:1,1->1,2->2,2->2,3->3,3





6:1,1->1,2->1,3->2,3->3,3

 




//Solution 1: Refer to the first path of the maze and search deep to find all paths of the maze



 



 



#include <bits/stdc++.h>





using namespace std;




//Can only go down or to the right: first down, then right.



int n,m;



int r[20][3];//Storing travel paths




//Changes in direction



int fx[3] = {0,1,0};



int fy[3] = {0,0,1}; 



int c;//register



 



void print(int k){



	c++;



	cout<<c<<":";



	//Except for the last point.



	for(int i = 1;i < k;i++){



		cout<<r[i][1]<<","<<r[i][2]<<"->";



	}



	cout<<n<<","<<m<<endl;



} 



 




//To the row of the r array with subscript k, record the x,y points



void dfs(int x,int y,int k){



	//Record coordinates



	r[k][1] = x;



	r[k][2] = y;



	



	//If it goes to the end, print the path



	if(x == n && y == m){



		print(k);



		//Stop the recursive function, when it reaches the end of the printout, there is no need to continue the recursion



		return; 



	} 



	



	int tx,ty;



	for(int i = 1;i <= 2;i++){



		tx = x + fx[i];



		ty = y + fy[i];



		



		//Determine the validity of tx,ty



		if(tx>=1&&tx<=n&&ty>=1&&ty<=m){



			dfs(tx,ty,k+1);



		} 



	}



} 



 



int main(){



	cin>>n>>m; 




	//The subscript to the r array is1The line that records the1,1point (in space or time)



	dfs(1,1,1);



}



 

 




//Solution 1: Refer to the first path of the maze and search deep to find all paths of the maze



 



 



#include <bits/stdc++.h>





using namespace std;




//Can only go down or to the right: first down, then right.



int n,m;



int r[20][3];//Storing travel paths




//Changes in direction



int fx[3] = {0,1,0};



int fy[3] = {0,0,1}; 



int c;//register



 



void print(int k){



	c++;



	cout<<c<<":";



	//Except for the last point.



	for(int i = 1;i < k;i++){



		cout<<r[i][1]<<","<<r[i][2]<<"->";



	}



	cout<<n<<","<<m<<endl;



} 



 




//To the row of the r array with subscript k, record the x,y points



void dfs(int x,int y,int k){



	//Record coordinates



	r[k][1] = x;



	r[k][2] = y;



	



	//If it goes to the end, print the path



	if(x == n && y == m){



		print(k);



		//Stop the recursive function, when it reaches the end of the printout, there is no need to continue the recursion



		return; 



	} 



	



	int tx,ty;



	for(int i = 1;i <= 2;i++){



		tx = x + fx[i];



		ty = y + fy[i];



		



		//Determine the validity of tx,ty



		if(tx>=1&&tx<=n&&ty>=1&&ty<=m){



			dfs(tx,ty,k+1);



		} 



	}



} 



 



int main(){



	cin>>n>>m; 




	//The subscript to the r array is1The line that records the1,1point (in space or time)



	dfs(1,1,1);



}



 

source (of information etc)

deep search recursive (calculation)