# Demo entry 6658414

big

Submitted by yyl on Nov 07, 2017 at 01:26
Language: C++. Code size: 1.6 kB.

```#include<cstdio>
#include<cmath>
#include<queue>
#include <algorithm>
#include <string>
using namespace std;
typedef struct step {
int x;
int y;
int num;
}step;
int map[7][10] = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },
{ 1, 1, 1, 0, 1, 1, 0, 0, 1, 1 },
{ 1, 1, 0, 1, 1, 0, 0, 1, 1, 1 },
{ 1, 1, 0, 1, 1, 0, 1, 1, 1, 1 },
{ 1, 1, 0, 0, 0, 1, 1, 1, 1, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },

};
int valid(step sat)
{
if (sat.x < 0 || sat.y <0  || sat.x >= 7 || sat.y >= 10) {
return 1;
}
if (map[sat.x][sat.y] == 1)
{
return 1;
}
return 0;
}

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int dbx[4] = { 1,-1,-1,1 };
int dby[4] = { 1,1,-1,-1 };
void bfs(step tmp)
{
queue<step> q;
q.push(tmp);
step p;
while (!q.empty())
{
p = q.front();
q.pop();
map[p.x][p.y] = 1;
int flag = 0;
for (int i = 0; i < 4; i++)
{
step next;
next.x = p.x + dx[i];
next.y = p.y + dy[i];
if (valid(next)==0) {
next.num = p.num + 1;
map[next.x][next.y] = 1;
q.push(next);
flag = 1;
if (next.x == 1 && next.y == 7)
{
printf("最短路径：%d\n", next.num);
}
}
}
if (flag == 0)
{
for (int i = 0; i < 4; i++)
{
step next;
next.x = p.x + dbx[i];
next.y = p.y + dby[i];
if (valid(next) == 0) {
next.num = p.num + 1;
map[next.x][next.y] = 1;
q.push(next);
if (next.x == 1 && next.y == 7)
{
printf("最短路径：%d\n", next.num);
}
}
}
}
}
}
int main()
{
step start = { 1,3,0 };
bfs(start);
}
```

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.