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