| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴一个一般般的代码
//我觉得需要注意的是递归的时候要对已经走过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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator