【lightoj-1046】Rider(BFS)

链接：http://www.lightoj.com/volume_showproblem.php?problem=1046

题意：

给m*n的棋盘，数字k代表这个位置上有棋子，并且一步可以连续跳1-k下，求所有棋子跳到同一位置的最小步数。

思路

容易想到用bfs，计算所有棋子在一个格子的步数，找出步数最小的格子就可以了。

 #include<bits/stdc++.h>

 using namespace std;

 char mp[][];

 int num[][], n, m;

 bool vis[][][];

 struct node

 {

     int x, y, step, jumpnum;

 };

 node s;

 void bfs(int cnt, int tiao)

 {

     int nx[][] = {{,},{,-},{,},{,-},{-,},{-,-},{-,},{-,-}};

     queue<node>Q;

     Q.push(s);

     while(!Q.empty())

     {

         s = Q.front();

         Q.pop();

         for(int k = ; k < ; k++)

         {

             node t = s; //这句一定要放在循环里！！之前放在外边一直WA..

             t.x = s.x + nx[k][];

             t.y = s.y + nx[k][];

             if(t.x<||t.x>=m||t.y<||t.y>=n||vis[cnt][t.x][t.y]) continue;

             if(t.jumpnum == )

             {

                 t.jumpnum = tiao;

                 vis[cnt][t.x][t.y] = ;

                 if(tiao == )  //若k=1那么也要步数+1

                     t.step = s.step+;

                 Q.push(t);

             }

             else if(t.jumpnum == tiao)

             {

                 t.step = s.step+;

                 t.jumpnum = s.jumpnum -;

                 vis[cnt][t.x][t.y] = ;

                 Q.push(t);

             }

             else                            //t.jumpnum减到1之前都不增加步数

             {

                 t.jumpnum = s.jumpnum -;

                 vis[cnt][t.x][t.y] = ;

                 Q.push(t);

             }

             num[t.x][t.y] += t.step;

         }

     }

 }

 int main()

 {

     int t, cas = ;

     cin>>t;

     //freopen("1.txt", "w", stdout);

     while(t--)

     {

         int cnt = ;

         memset(num, , sizeof num);

         memset(vis, , sizeof vis);

         scanf("%d%d", &m, &n);

         for(int i  = ; i < m; i++)

             scanf("%s", mp[i]);

         for(int i = ; i < m; i++)

             for(int j = ; j < n; j++)

             {

                 if(mp[i][j] != '.')

                 {

                     vis[++cnt][i][j] = ;

                     s.x = i, s.y = j, s.jumpnum = mp[i][j]-'', s.step = ;

                     bfs(cnt, mp[i][j]-'');

                 }

             }

         int ans = 1e9, ii, jj, k;

         for(int i = ; i < m; i++)

             for(int j = ; j < n; j++)

             {

                 for(k =  ; k <= cnt; k++)

                     if(!vis[k][i][j]) break;

                 if(k==cnt+&&ans > num[i][j])

                     ans = num[i][j], ii = i, jj = j;

             }

         printf("Case %d: %d\n", ++cas, ans==1e9?-:ans);

     }

 }