關(guān)于常見矩陣路徑計算問題(iOS版本)
常見類型介紹：
- /*●問題描述：
給出一個矩陣，其中0表示通路，1表示墻壁稿湿，這樣就形成了一個迷宮，要求編寫算法求出其中一條路徑押赊。
●遞歸思路：
編寫一個走迷宮函數(shù)饺藤，傳入二位數(shù)組的下標(biāo)，先假設(shè)該點位于最終路徑上（將0置為2）再探測周圍四個點是否可以走通（是否為０）流礁，如果可以走通則將該點四周能走通的點作為函數(shù)參數(shù)傳入函數(shù)進入遞歸涕俗。若四周均不能走通（都不為０時）則將該點置回０表示該點不是最終路徑上的點。
在此思路中遞歸進入時表示了枚舉路徑神帅，當(dāng)發(fā)現(xiàn)此條路徑走到某處再不能走通時就將路徑該點置回０并且遞歸退出（回溯）尋找下一條可走通路徑再姑。
*/
/*
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
*/
規(guī)則中可以上下左右方向前進，求左上角到右下角的最小步數(shù)：
核心在于遞歸回溯判斷找御，下面貼出代碼
int mazeChat(int maze[][5],int i,int j){
int end = 0;
maze[i][j] = 2;
//如果到終點直接置為1
if (i == END_I && j == END_J) {
end = 1;
}
//不是終點則按照右下左上判斷
if (end !=1 && j+1<=END_J && maze[i][j+1] == 0) {
if (mazeChat(maze, i, j+1) == 1) {
return 1;
}
}
if (end !=1 && i+1<=END_I && maze[i+1][j] == 0) {
if (mazeChat(maze, i+1, j)==1) {
return 1;
}
}
if (end !=1 && j-1>=START_J && maze[i][j-1] == 0) {
if (mazeChat(maze, i, j-1) == 1) {
return 1;
}
}
if (end !=1 && i-1>=START_I && maze[i-1][j] == 0) {
if (mazeChat(maze, i-1, j)==1) {
return 1;
}
}
//四周都沒有路
if (end !=1) {
maze[i][j] = 0;
}
return end;
}
方法調(diào)用：
if (mazeChat(maze, 0, 0) == 0) {
printf("沒有通道");
return;
}else{
printf("有通道\n");
}
路徑會在后面的打印中根據(jù)我們預(yù)先設(shè)定的值去判斷：
附上地址：demo
2.最短路徑和計算：
【問題描述】: 給出一個矩陣元镀，從左上角開始走，只能向右或者向下霎桅，所有數(shù)字累加就是路徑和栖疑，求出其中最小路徑。
{1,3,5,9},
{8,1,3,4},
{5,0,6,1},
{8,8,4,0}
先說一共有多少種走法:因為只能向右或者向下滔驶，所以數(shù)學(xué)方向考慮只有向右3次向下三次即可遇革，所以簡單的C6-3 即可
//走法
int uniquePaths(int m, int n)
{
int N = n + m - 2;
int K = n - 1;
double res = 1.0;
for (int i = 1; i <= n - 1; i++)
{
res = res * (N - K + i) / i;
}
return (int)res;
}
關(guān)于這個問題：
/*
【問題描述】: 給出一個矩陣，從左上角開始走揭糕，只能向右或者向下萝快，所有數(shù)字累加就是路徑和，求出其中最小路徑插佛。
思路：只允許向右或者向下走 所以開始計算時當(dāng)前s[i][j]只可能從s[i-1][j]+data[i][j]或者s[i][j-1]+data[i][j]計算得到
也就是s[i][j] = min(s[i-1][j],s[i][j-1])+ data[i][j] 即需要比較s[i-1][j],s[i][j-1])
因為第一行沒有s[i-1][j]元素杠巡，只有s[i][j-1]元素。
第一列沒有s[i][j-1]元素雇寇，只有s[i-1][j]元素氢拥。
需要特殊處理
*/
我們通過比較每一個位置左邊和上邊大小而重新對該位置的值進行求和賦值即可得到一個全新的矩陣，取矩陣最后一個值即是我們需要的路徑最短之和：
重新賦值矩陣方法：
//獲取行數(shù)和列數(shù)
int rows = ROWS;
int cols = COLS;
//第一列
for (int i = 1; i < rows; i++)
{
data[i][0] = data[i - 1][0] + data[i][0];
}
//第一行
for (int i = 1; i < cols; i++)
{
data[0][i] = data[0][i - 1] + data[0][i];
}
//非第一行和第一列的元素
for (int i = 1; i < rows; i++)
{
for (int j = 1; j < cols; j++)
{
if (data[i][j-1] > data[i-1][j]) {
data[i][j] = data[i - 1][j] + data[i][j];
}else{
data[i][j] = data[i][j - 1] + data[i][j];
}
}
}
//返回最短路徑值
return data[rows - 1][cols - 1];
拿到最小路徑和的同時也可以通過得到的新矩陣去正推或者逆推得到路徑下標(biāo)的走法（這種重新賦值矩陣的方法優(yōu)點在于只需要遍歷一次即可拿到所有想要的結(jié)果锨侯，時間和空間復(fù)雜度低嫩海。缺點在于過程中存在的零時變量太多，所以之后得到新矩陣后才去獲得路徑下標(biāo)）囚痴；
兩種推算路徑下標(biāo)方法：
printf("最優(yōu)路徑坐標(biāo):\n");
int rowt = 3;
int colt = 3;
for (int i = 0; i < 7; i++) {
printf("(%d,%d)\n",rowt,colt);
if(data[rowt-1][colt] < data[rowt][colt-1]){
rowt--;
}
else{
colt--;
}
}
int g = 0;
int k = 0;
for (int j = 0; j<7; j++) {
printf("{%d,%d}",g,k);
if (data[g][k+1] < data[g+1][k]) {
k++;
}else{
g++;
}
}
附上地址：demo
