每日一题3.30.2
每日一题3.30.2
代码实现:
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int map[10][10];
int vis[10][10];
int n, m;
int head, rear;
//四个方向
int dx[4] = { 0, 1, -1, 0 };
int dy[4] = { 1, 0, 0, -1 };
struct node{
int x;
int y;
int pre;
}num[1100];
void print(int n)
{
if (num[n].pre != -1){
print(num[n].pre);
printf("(%d,%d)\n", num[n].x, num[n].y);
}
}
void bfs(){
head = 0;
rear = 0;
num[rear].x = 0, num[rear].y = 0, num[rear++].pre = -1;
while (head<rear){
for (int i = 0; i<4; i++){ //四个方向搜搜搜
int bj1 = num[head].x + dx[i];
int bj2 = num[head].y + dy[i];
if (bj1 >= n || bj2 >= m || bj1<0 || bj2<0 || map[bj1][bj2] == 1)
continue;
map[bj1][bj2] = 1;
num[rear].x = bj1;
num[rear].y = bj2;
num[rear].pre = head;
rear++;
if (bj1 == n - 1 && bj2 == m - 1) //到达终点
print(head);
}
head++;
}
}
int main()
{
while (cin >> n >> m)
{
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
scanf("%d", &map[i][j]);
}
}
printf("(0,0)\n");
bfs();
printf("(%d,%d)\n", n - 1, m - 1);
}
system("pause");
return 0;
}
参考答案: