UC知道最少转弯问题？ c++
来源：百度知道 编辑：UC知道 时间：2024/05/28 12:56:37
有一个m*n的方格，每个格里写着0或1，1代表有障碍物，0代表平地。你要从一个地方走到另一个地方，只能走相邻的格子，不许斜走。
输入m，n（即宽高）地形
（例如：
1 1 0 1 0
0 0 0 0 0
）
差不多就这个样子吧，然后输入起点和终点的坐标（如：3 1 5 1）（第三列第一行，第五列第一行），求出最少要拐几个弯。例如这张图，就应该拐2个弯。
样例输入：
5 2
1 1 0 1 0
0 0 0 0 0
3 1 5 1
样例输出：
2
怎么做？用C++。最好用递归~谢谢啦！
输入m，n（即宽高）地形
（例如：
1 1 0 1 0
0 0 0 0 0
）
差不多就这个样子吧，然后输入起点和终点的坐标（如：3 1 5 1）（第三列第一行，第五列第一行），求出最少要拐几个弯。例如这张图，就应该拐2个弯。
样例输入：
5 2
1 1 0 1 0
0 0 0 0 0
3 1 5 1
样例输出：
2
怎么做？用C++。最好用递归~谢谢啦！
用的是动态规划算法，采用的是记忆化搜索
#include <iostream>
using namespace std;
const int Limit_Size = 1000;
const int Max_int = 0xfffffff;
int m, n, g[ Limit_Size ][ Limit_Size ];
int opt[ 5 ][ Limit_Size ][ Limit_Size ];
int x1, y1, x2, y2;
bool visit[ Limit_Size ][ Limit_Size ];
struct directs
{
int a, b;
}direct[ 4 ];
void read_graph( )
{
int i, j, k;
cin >> m >> n;
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; j++ )
{
visit[ i ][ j ] = false;
cin >> g[ i ][ j ];
for ( k = 0; k <= 4; k++ )
opt[ k ][ i ][ j ] = -1;
}
cin >> y1 >> x1 >> y2 >> x2;
direct[ 0 ].a = 1; direct[ 0 ].b = 0;
direct[ 1 ].a = 0; direct[ 1 ].b = 1;
direct[ 2 ].a = -1; direct[ 2 ].b = 0;
direct[ 3 ].a = 0; direct[ 3 ].b = -1;
}
int dfs( int x, int y,