Snakes & Ladders ——BFS入门题

April 17, 2013
BFS

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=116&page=show_problem&problem=555 题目大意：　　给一个棋盘，分布着蛇和梯子，投骰子确定走的步数，问最少投几次骰子可以到达终点，到达蛇头就回到蛇尾，到达梯子底部就上升到梯子顶部。思路：　　BFS，到达每一个节点都可以扩展出6个节点，判断终点是不是到达过，如果到达过，退出循环。这题WA了……


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
int D, N , S, L, a[23*23], b[23*23];
typedef struct La{
  int start, end;
}La;
La la[120];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("arb.in", "r", stdin);
#endif
  scanf("%d", &D);
  while (D--){
    scanf("%d%d%d", &N, &S, &L); int i , j, k, s;
    for (i = 1; i <= S + L; ++i){
      scanf("%d%d", &la[i].start, &la[i].end);
    } memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b)); b[1] = 1;
    int cnt = 0; bool flag = false;
    while (a[N*N] == 0){
      memcpy(a, b, sizeof(b));
      memset(b, 0, sizeof(b));
      for (i = 1; i < N*N; ++i){
        if (!a[i]) continue;
        for (j = 1; j <= 6; ++j){
          if (j + i > N*N) break;
          flag = false;
          for (k = 1; k <= L + S; ++k){
            if (j + i == la[k].start){
              b[la[k].end] = 1; flag = true;
            }
          }
          if (!flag && !b[i+j]) b[i+j] = 1;
        }
      } cnt++;
    }
    cout << cnt-1 << endl;
  }

  return 0;
}

交了，WA……

Read more