Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贴一个一般般的代码

Posted by a280920481 at 2018-10-11 21:10:20 on Problem 3009
```//我觉得需要注意的是递归的时候要对已经走过10步以上的情况进行剪枝，否则会超时

#include <queue>
#include <iostream>
using namespace std;

struct situ
{
int x;
int y;
int t;
};
const int px[4] = { -1,0,0,1 };
const int py[4] = { 0,-1,1,0 };
int aa[20][20];// 0 - 空地  1 - 障碍  2 - 起点  3 - 终点
int mx = 0, my = 0;//地图大小

void solve(int x, int y, int t);

int nans = 0;
int ansstep = 11;

int main()
{
int beginx = 0, beginy = 0;
while (true)
{
ansstep = 11;
nans = 0;
scanf_s("%d%d", &my, &mx);
if (mx == 0 || my == 0)
{
return 0;
}
for (int i = 0; i < mx; i++)
{
for (int t = 0; t < my; t++)
{
scanf_s("%d", &aa[i][t]);
if (aa[i][t] == 2)
{
beginx = i;
beginy = t;
}
}
}
solve(beginx, beginy, 1);

if (ansstep > 10)
{
cout << -1 << endl;
}
else
{
printf_s("%d\n", ansstep);
}

}

}
void solve(int x, int y, int t)
{
int lx, ly;
if (t > 10)
{
return;
}
for (int i = 0; i < 4; i++)//对于4个方向
{
lx = x;
ly = y;
while (true)
{
lx += px[i];
ly += py[i];
if (lx >= 0 && lx < mx && ly >= 0 && ly < my)//没有超界
{
if (aa[lx][ly] == 1)//如果前方是障碍
{
if (((lx - px[i]) != x) || ((ly - py[i]) != y))
{
aa[lx][ly] = 0;
solve(lx - px[i], ly - py[i], t + 1);
aa[lx][ly] = 1;//回溯
}
break;
}
else if (aa[lx][ly] == 3)//如果前方是终点
{
if (t < ansstep)
{
ansstep = t;
}
break;
}
}
else//如果超界则剪枝
{
break;
}
}

}
return;
}```

Followed by: