最少步數
時間限制: 3000 ms | 記憶體限制: 65535 KB 難度: 4
- 描述
-
這有一個迷宮,有0~8行和0~8列:
1,1,1,1,1,1,1,1,1
1,0,0,1,0,0,1,0,1
1,0,0,1,1,0,0,0,1
1,0,1,0,1,1,0,1,1
1,0,0,0,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,1,0,0,1
1,1,0,1,0,0,0,0,1
1,1,1,1,1,1,1,1,1
0表示道路,1表示牆。
現在輸入一個道路的坐标作為起點,再如輸入一個道路的坐标作為終點,問最少走幾步才能從起點到達終點?
(注:一步是指從一坐标點走到其上下左右相鄰坐标點,如:從(3,1)到(4,1)。)
- 輸入
-
第一行輸入一個整數n(0<n<=100),表示有n組測試資料;
随後n行,每行有四個整數a,b,c,d(0<=a,b,c,d<=8)分别表示起點的行、列,終點的行、列。
輸出 - 輸出最少走幾步。 樣例輸入
-
2 3 1 5 7 3 1 6 7
樣例輸出 -
12 11
-
比較典型的DFS
#include<stdio.h>
int map[9][9] = { {1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,1,0,1},
{1,0,0,1,1,0,0,0,1},
{1,0,1,0,1,1,0,1,1},
{1,0,0,0,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,1,0,0,1},
{1,1,0,1,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1}};
int a[4] = {0, 1, 0, -1}, b[4] = {1, 0, -1, 0};
int m, n, num, ans;//num計算步數, ans計算最短步數
void dfs(int x, int y, int num) {
int q = 0, k = 0, u, v;
if(x == m && y == n)
if(num < ans)//這裡可能有些難了解 其實是回溯過程
ans = num;
while(!q && k < 4) {
u = x + a[k];
v = y + b[k];
if(u < 9 && u >= 0 && v < 9 && u >= 0 && map[u][v] == 0) {
map[u][v] = 1;
dfs(u, v, num+1);
map[u][v] = 0;
}
k++;
}
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int x, y;
ans = 99999;
scanf("%d%d%d%d", &x, &y, &m, &n);
dfs(x, y, 0);
printf("%d\n", ans);
}
}
打表觀察回溯過程
2
3 1 5 7
num = 14
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0 1
1 0 0 1 1 0 0 0 1
1 * 1 0 1 1 0 1 1
1 * * * * 1 0 0 1
1 1 0 1 * 1 * * 1
1 1 0 1 * 1 * * 1
1 1 0 1 * * * * 1
1 1 1 1 1 1 1 1 1
num = 16
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0 1
1 0 0 1 1 0 0 0 1
1 * 1 0 1 1 0 1 1
1 * * * * 1 * * 1
1 1 0 1 * 1 * * 1
1 1 0 1 * 1 * * 1
1 1 0 1 * * * * 1
1 1 1 1 1 1 1 1 1
num = 12
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0 1
1 0 0 1 1 0 0 0 1
1 * 1 0 1 1 0 1 1
1 * * * * 1 0 0 1
1 1 0 1 * 1 0 * 1
1 1 0 1 * 1 0 * 1
1 1 0 1 * * * * 1
1 1 1 1 1 1 1 1 1
num = 12
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0 1
1 0 0 1 1 0 0 0 1
1 * 1 0 1 1 0 1 1
1 * * * * 1 0 0 1
1 1 0 1 * 1 0 * 1
1 1 0 1 * 1 * * 1
1 1 0 1 * * * 0 1
1 1 1 1 1 1 1 1 1
num = 12
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0 1
1 0 0 1 1 0 0 0 1
1 * 1 0 1 1 0 1 1
1 * * * * 1 0 0 1
1 1 0 1 * 1 * * 1
1 1 0 1 * 1 * 0 1
1 1 0 1 * * * 0 1
1 1 1 1 1 1 1 1 1
num = 14
1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 1 0 1
1 0 0 1 1 0 0 0 1
1 * 1 0 1 1 0 1 1
1 * * * * 1 * * 1
1 1 0 1 * 1 * * 1
1 1 0 1 * 1 * 0 1
1 1 0 1 * * * 0 1
1 1 1 1 1 1 1 1 1
#include<stdio.h>
#include<string.h>
char map[9][10] = {"111111111", "100100101", "100110001", "101011011",
"100001001", "110101001", "110101001", "110100001", "111111111" };
int a[4] = {0, 1, 0, -1}, b[4] = {1, 0, -1, 0}, m, n, num;
void dfs(int x, int y, int num) {
int q = 0, k = 0, u, v;
if(x == m && y == n) {
printf("num = %d\n", num);
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++)
printf("%c ", map[i][j]);
printf("\n");
}
}
while(q == 0 && k < 4) {
u = x + a[k];
v = y + b[k];
if(u < 9 && u >= 0 && v < 9 && u >= 0 && map[u][v] == '0') {
map[u][v] = '*';
dfs(u, v, num+1);
map[u][v] = '0';
}
k++;
}
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int x, y;
scanf("%d%d%d%d", &x, &y, &m, &n);
map[x][y] = '*';
dfs(x, y, 0);
}
}
//用來觀察路線的代碼...