Codeforces Beta Round #3

点击打开链接

A

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;

#define MAXN 500010
#define N 10

int ans , end;
int sx , sy , ex , ey;
int vis[N][N];
int dir[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
char mp[N][N];
struct Point{
   int x;
   int y;
   int pre;
   int d;
   int step;
}p[MAXN];

void init(){
    strcpy(mp[0] , "U");
    strcpy(mp[1] , "RU");
    strcpy(mp[2] , "R");
    strcpy(mp[3] , "RD");
    strcpy(mp[4] , "D");
    strcpy(mp[5] , "LD");
    strcpy(mp[6] , "L");
    strcpy(mp[7] , "LU");
}

void BFS(){
    int front , rear;
    front = 0 , rear = 1;

    memset(vis , 0 , sizeof(vis));
    p[front].x = sx , p[front].y = sy;
    p[front].pre = 0 , p[front].step = 0;
    vis[sx][sy] = 1;

    while(front < rear){
       Point tmp = p[front];/*取出队列的头然后头指针加加*/
       if(tmp.x == ex && tmp.y == ey){
          end = front;
          ans = tmp.step;
          break;
       }
       front++;
       for(int i = 0 ; i < 8 ; i++){
          if(tmp.x+dir[i][0] <= 0 || tmp.x+dir[i][0] > 8)
            continue;
          if(tmp.y+dir[i][1] <= 0 || tmp.y+dir[i][1] > 8)
            continue;
          if(vis[tmp.x+dir[i][0]][tmp.y+dir[i][1]])
            continue;
          vis[tmp.x+dir[i][0]][tmp.y+dir[i][1]] = 1;
          p[rear].x = tmp.x+dir[i][0] , p[rear].y = tmp.y+dir[i][1];
          p[rear].pre = front-1;
          p[rear].d = i;
          p[rear++].step = tmp.step+1;
       }
    }
}

void output(int x){
    if(x == 0)
      return;
    output(p[x].pre);
    printf("%s\n" , mp[p[x].d]);
}

int main(){
    string str1 , str2;
    init();
    while(cin>>str1>>str2){
       ans = 0;
       sx = str1[0]-'a'+1 , sy = str1[1]-'0';
       ex = str2[0]-'a'+1 , ey = str2[1]-'0';

       BFS();
       printf("%d\n" , ans);
       output(end);
    }
    return 0;
}