织梦模板怎么验证网站,cms 网站后台,装修网站制作设计价格费用,佛山seo整站优化题面 Mike同学在为扫地机器人设计一个在矩形区域中行走的算法#xff0c;Mike是这样设计的#xff1a;先把机器人放在出发点 (1,1)(1,1) 点上#xff0c;机器人在每个点上都会沿用如下的规则来判断下一个该去的点是哪里。规则#xff1a;优先向右#xff0c;如果向右不能走…题面 Mike同学在为扫地机器人设计一个在矩形区域中行走的算法Mike是这样设计的先把机器人放在出发点 (1,1)(1,1) 点上机器人在每个点上都会沿用如下的规则来判断下一个该去的点是哪里。规则优先向右如果向右不能走比如右侧出了矩形或者右侧扫过了则尝试向下向下不能走则尝试向左向左不能走则尝试向上直到所有的点都扫过。 Mike为了验证自己设计的算法是否正确打算先模拟一下这个算法每当机器人走过一个单元格时会在单元格内标记一个数字这个数字从 11 开始每经过一个单元格数字会递增 11 直到所有的单元格都扫一遍也就是所有的单元格都标记过数字机器人会自动停止。 请你帮助Mike设计一个程序按照上面的规则将一个 n×m 大小的矩形标记一下数字输出最终标记的结果。 输入 一行内有 22 个两个整数 n 和 m 用空格隔开分别代表矩形区域的行数高和列数宽。 1n,m10。 输出 输出按题意机器人走过每个点之后标记数字的结果每个数字输出时场宽设置为 3。 链接Link. 最基础的dfs题根据题目右下左上得顺序递归即可要注意不能出边界和不重复走
解法1递归前暴力判断
#include bits/stdc.h
using namespace std;
int n , m;
int a[20][20];
void dfs(int x , int y , int k){a[x][y] k;if (y 1 m a[x][y1] 0 )dfs(x , y 1 , k 1);if (x 1 n a[x1][y] 0 )dfs(x 1 , y , k 1);if (y - 1 1 a[x][y-1] 0 )dfs(x , y - 1 , k 1);if (x - 1 1 a[x-1][y] 0 )dfs(x - 1 , y , k 1);
}int main(){scanf(%d%d , n , m);dfs(1,1,1);for ( int i 1 ; i n ; i ){for ( int j 1 ; j m ; j )cout setw(3) a[i][j];printf(\n);}return 0;
}
解法2在递归前先大判断再暴力尝试
#include bits/stdc.h
using namespace std;
int n , m;
int a[20][20];
void dfs(int x , int y , int k){if(x 1 x n y 1 y m a[x][y] 0 ){a[x][y] k;dfs(x , y 1 , k 1);dfs(x 1 , y , k 1);dfs(x , y - 1 , k 1);dfs(x - 1 , y , k 1);}}int main(){scanf(%d%d , n , m);dfs(1,1,1);for ( int i 1 ; i n ; i ){for ( int j 1 ; j m ; j )cout setw(3) a[i][j];printf(\n);}return 0;
} 解法3在递归前先大判断再用方向数组循环尝试
#include bits/stdc.h
using namespace std;
int n , m;
int a[20][20];
int fx[5] {0 , 0 , 1 , 0 , -1} , fy[5] {0 , 1 , 0 , -1 , 0};
void dfs(int x , int y , int k){if(x 1 x n y 1 y m a[x][y] 0 ){a[x][y] k;int tx , ty;for ( int i 1 ; i 4 ; i ){tx x fx[i];ty y fy[i];dfs(tx , ty , k1);}}}int main(){scanf(%d%d , n , m);dfs(1,1,1);for ( int i 1 ; i n ; i ){for ( int j 1 ; j m ; j )cout setw(3) a[i][j];printf(\n);}return 0;
} 解法4用方向数组循环尝试 在每次递归前判断决定是否递归
#include bits/stdc.h
using namespace std;
int n , m;
int a[20][20];
int fx[5] {0 , 0 , 1 , 0 , -1} , fy[5] {0 , 1 , 0 , -1 , 0};
void dfs(int x , int y , int k){a[x][y] k;int tx , ty;for ( int i 1 ; i 4 ; i ){tx x fx[i];ty y fy[i]; if(tx 1 tx n ty 1 ty m a[tx][ty] 0 )dfs(tx , ty , k1); }}int main(){scanf(%d%d , n , m);dfs(1,1,1);for ( int i 1 ; i n ; i ){for ( int j 1 ; j m ; j )cout setw(3) a[i][j];printf(\n);}return 0;
}
