ural 1008 Image Encoding BFS

/*

 

题目：给出两种图形的像素表示方法，现在给出其中一种，求另一种的像素表示方法。

分析：BFS的思想

 

*/

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

 

const int X = 15;

 

struct node{

    int x,y;

};

 

int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};//右上左下的方向偏移量

char d[] = "RTLB";

bool use[X][X],map[X][X];

vector<int> ans[200];

int pos;

 

bool check(int x,int y){ //判断是否符合

    if(x<1||y<1||x>10||y>10) //越界

        return false;

    if(!map[x][y]||use[x][y])   //若不为黑色或者已经访问过的

        return false;

    return true;

}

 

void bfs(int sx,int sy){//给出黑色的位置，求字母的表示方法，上下左右的储存方式用向量vector来储存

    memset(use,false,sizeof(use));

    pos = 0;

 

    node cur,temp;

 

    cur.x = sx;

    cur.y = sy;

    queue<node> q;

    q.push(cur);

 

    use[sx][sy] = true;

    while(!q.empty()){

        cur = q.front();

        q.pop();

        for(int i=0;i<4;i++){

            temp.x = cur.x+dir[i][0];

            temp.y = cur.y+dir[i][1];

            if(check(temp.x,temp.y)){

                q.push(temp);

                use[temp.x][temp.y] = true;

                ans[pos].push_back(i);

            }

        }

        pos++;

    }

    int len;

   cout<<sx<<" "<<sy<<endl;

    for(int i=0;i<pos;i++){

        len = ans[i].size();

        for(int j=0;j<len;j++)

            cout<<d[ans[i][j]];

        if(i!=pos-1)

            cout<<","<<endl;

        else

            cout<<"."<<endl;

    }

}

 

void bfs_2(int sx,int sy){  //给出字母的表示方法，求坐标的表示方法

   node cur,temp;

   queue<node> q;

   memset(map,false,sizeof(map));

   cur.x = sx;

   cur.y = sy;

   q.push(cur);

   char s[10];

   int len,cnt = 1;

   while(q.size()){

      cur = q.front();

      map[cur.x][cur.y] = true;

      q.pop();

      scanf("%s",s);

      len = strlen(s);

      if(len==1)

         continue;

      cnt += len-1;

      for(int i=0;i<len-1;i++){

         if(s[i]=='R'){

            temp.x = cur.x+1;

            temp.y = cur.y;

            q.push(temp);

         }

         else if(s[i]=='T'){

            temp.x = cur.x;

            temp.y = cur.y+1;

            q.push(temp);

         }

         else if(s[i]=='L'){

            temp.x = cur.x-1;

            temp.y = cur.y;

            q.push(temp);

         }

         else{

            temp.x = cur.x;

            temp.y = cur.y-1;

            q.push(temp);

         }

      }

   }

   cout<<cnt<<endl;

   for(int i=0;i<X;i++)  //先按x的由小到大输出，若相同再按y的由小到大输出

      for(int j=0;j<X;j++)

         if(map[i][j])

            cout<<i<<" "<<j<<endl;

}

 

void input(){   //输入函数

    int x,y,z;

    cin>>x;

    if(getchar()=='\n'){ //如果第一行只有一个数字输入，表示输入的是用坐标的方式来表示像素

        int sx = 10000,sy;

        memset(map,false,sizeof(map));

        for(int i=0;i<x;i++){

            scanf("%d%d",&y,&z);

            map[y][z] = true;

            if(y<sx){

                sx = y;

                sy = z;

            }

        }

        bfs(sx,sy);

    }

    else{

      scanf("%d",&y);

      bfs_2(x,y);

    }

}

int main(){

    freopen("sum.in","r",stdin);

    freopen("sum.out","w",stdout);

    input();

    return 0;

}