来自"NOCOW"

---

Solution From format_jam: a problem about simple BFS(Breadth-First-Search）

---

const h:array[1..4,1..2] of integer=((1,0),(0,1),(-1,0),(0,-1));
      ch:array[1..4] of char=('R','T','L','B');
      hh:Array[1..4,1..2] of integer=((1,0),(0,1),(-1,0),(0,-1));
 
var ans:array[1..100] of string[5];
    cans,tem,b,e,a,n,i,j:longint;
    x,y:array[1..100] of longint;
    visit,exist:array[0..11,0..11] of boolean;
    cha:string;
    temp:array[1..10] of integer;
procedure extend(tx,ty:longint);
var i:longint;
begin
  inc(cans);
  for i:=1 to 4 do
    if exist[tx+h[i,1],ty+h[i,2]] and not visit[tx+h[i,1],ty+h[i,2]] then
    begin
      x[tem]:=tx+h[i,1];
      y[tem]:=ty+h[i,2];
      inc(tem);
      visit[tx+h[i,1],ty+h[i,2]]:=true;
      ans[cans]:=ans[cans]+ch[i];
    end;
  ans[cans]:=ans[cans]+',';
end;
 
procedure work1;
begin
  read(a,b);
  exist[a,b]:=true;
  x[1]:=a;y[1]:=b;
  for i:=1 to n-1 do
  begin
     read(a,b);
     exist[a,b]:=true;
  end;
  visit[x[1],y[1]]:=true;
  b:=1;e:=2;
  while b<>e do
  begin
    tem:=e;
    for i:=b to e-1 do
      extend(x[i],y[i]);
    b:=e;
    e:=tem;
  end;
  writeln(x[1],' ',y[1]);
  for i:=1 to cans-1 do
     writeln(ans[i]);
  writeln('.');
end;
 
function return(x:char):integer;
begin
  if x='R' then exit(1);
  if x='T' then exit(2);
  if x='L' then exit(3);
  if x='B' then exit(4);
end;
procedure swap(var a,b:longint);
begin
  if a=b then exit;
  a:=a xor b;
  b:=a xor b;
  a:=a xor b;
end;
 
procedure sort;
var t,i,j:longint;
begin
  t:=tem-1;
  for i:=1 to t-1 do
    for j:=i+1 to t do
     if (x[i]>x[j])or((x[i]=x[j])and(y[i]>y[j])) then
       begin
         swap(x[i],x[j]);
         swap(y[i],y[j]);
       end;
end;
 
procedure work2;
begin
  x[1]:=a;y[1]:=b;
  tem:=1;
  b:=1;e:=2;
  while b<>e do
  begin
    tem:=e;
    for i:=b to e-1 do
    begin
      readln(cha);
      for j:=1 to length(cha)-1 do
      begin
        x[tem]:=x[i]+hh[return(cha[j]),1];
        y[tem]:=y[i]+hh[return(cha[j]),2];
        inc(tem);
      end;
    end;
    b:=e;
    e:=tem;
  end;
  sort;
  writeln(tem-1);
  for i:=1 to tem-1 do
    writeln(x[i],' ',y[i]);
end;
 
begin
  while not eoln do begin inc(i);read(temp[i]);end;
  if i=1 then begin n:=temp[1];work1;end else
  if i=2 then begin a:=temp[1];b:=temp[2];readln;work2;end;
end.

yuanyuan's solution:

program p1008;
const
  dx:array[1..4] of integer=(1,0,-1,0);
  dy:array[1..4] of integer=(0,1,0,-1);
  c:array[1..4] of char=('R','T','L','B');
var
  s:shortstring;
  n,i,j,head,tail:integer;
  x,y:array[1..100] of integer;
  map,b:array[0..11,0..11] of boolean;
procedure change1;
  begin
    fillchar(map,sizeof(map),false);
    for i:=1 to n do
      begin
        readln(x[i],y[i]);
        map[x[i],y[i]]:=true;
      end;
    writeln(x[1],' ',y[1]);
    b[x[1],y[1]]:=true;
    head:=1;tail:=1;
    while head<=tail do
      begin
        for i:=1 to 4 do
          if (map[x[head]+dx[i],y[head]+dy[i]]) and not(b[x[head]+dx[i],y[head]+dy[i]]) then
            begin
              write(c[i]);
              b[x[head]+dx[i],y[head]+dy[i]]:=true;
              inc(tail);
              x[tail]:=x[head]+dx[i];y[tail]:=y[head]+dy[i];
            end;
        if head<tail
          then writeln(',')
          else writeln('.');
        inc(head);
      end;
  end;
procedure change2;
  function getk(ch:char):integer;
    begin
      case ch of
        'R':exit(1);
        'T':exit(2);
        'L':exit(3);
        'B':exit(4);
      end;
    end;
  procedure swap(var a,b:integer);
    begin
      if a=b then exit;
      a:=a xor b;
      b:=a xor b;
      a:=a xor b;
    end;
  begin
    x[1]:=i;y[1]:=j;
    b[i,j]:=true;
    head:=1;tail:=1;
    while head<=tail do
      begin
        readln(s);
        for i:=1 to length(s)-1 do
          begin
            j:=getk(s[i]);
            if not(b[x[head]+dx[j],y[head]+dy[j]]) then
              begin
                b[x[head]+dx[j],y[head]+dy[j]]:=true;
                inc(tail);
                x[tail]:=x[head]+dx[j];y[tail]:=y[head]+dy[j];
              end;
          end;
        inc(head);
      end;
    n:=tail;
    for i:=1 to n-1 do
      for j:=i+1 to n do
        if (x[i]>x[j]) or ((x[i]=x[j]) and (y[i]>y[j])) then
          begin
            swap(x[i],x[j]);
            swap(y[i],y[j]);
          end;
    writeln(n);
    for i:=1 to n do
      writeln(x[i],' ',y[i]);
  end;
begin
  readln(s);
  fillchar(b,sizeof(b),false);
  if pos(' ',s)=0
    then begin
           val(s,n);
           change1;
         end
    else begin
           val(copy(s,1,pos(' ',s)-1),i);
           val(copy(s,pos(' ',s)+1,length(s)-pos(' ',s)),j);
           change2;
         end;
end.

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

---

（来自田田） 发现这的CPP程序太少，加几个吧，希望大家可以多多交流。 这个代码写的不是很好，懒得改了，表示一下歉意，细心点的话应该看的懂。input 和BFS1是第一种情况的 BFS2是第二种情况（后来加的） 这题是两种情况可以互相转换，我就是刚开始只看示例一种情况。

---

#include<iostream>
#include<queue>
#include<string.h>
#include<string>
using  namespace std;
 
typedef struct point
{int x,y; } point;
 
bool graph[12][12]={0};
bool f[12][12]={0};
bool print[12][12]={0};
 
int n;
int lbx=10,lby=10;
 
void input()
{
     int x,y;
     for(int i=1; i<=n; i++)
         {
              cin>>x>>y; graph[x][y]=1;
              if(x<lbx){ lbx=x; lby=y; }
              else if(x==lbx&&y<lby)
                    lby=y;
         }
}
 
void BFS1()    //数字情况 
{
     queue<point> q;
     point temp; temp.x=lbx; temp.y=lby;
     cout<<lbx<<' '<<lby<<endl;
     q.push(temp);
     int x,y; int cnt=0;
     print[lbx][lby]=1;
     while(q.size())
     {
              temp=q.front(); q.pop();
              x=temp.x; y=temp.y;
              if(f[x][y]==1)continue;
              f[x][y]=1;
              if(graph[x+1][y]==1&&!f[x+1][y]){if(!print[x+1][y]) cout<<'R'; print[x+1][y]=1; temp.x=x+1;temp.y=y; q.push(temp);}
              if(graph[x][y+1]==1&&!f[x][y+1]){if(!print[x][y+1]) cout<<'T'; print[x][y+1]=1; temp.x=x;temp.y=y+1; q.push(temp);}
              if(graph[x-1][y]==1&&!f[x-1][y]){if(!print[x-1][y]) cout<<'L'; print[x-1][y]=1; temp.x=x-1;temp.y=y; q.push(temp);}
              if(graph[x][y-1]==1&&!f[x][y-1]){if(!print[x][y-1]) cout<<'B'; print[x][y-1]=1; temp.x=x;temp.y=y-1; q.push(temp);}
              ++cnt;
              if(cnt==n) cout<<'.'<<endl;
               else  cout <<','<<endl;
     }
}
 
void BFS2()  // 
{
     lbx=n; cin>>lby;
     queue<point>q;
     point temp; temp.x=lbx; temp.y=lby;
     q.push(temp);
     string str; int x,y;
     graph[lbx][lby]=1;
     while(q.size())
     {
 
        temp=q.front(); q.pop();
        x=temp.x; y=temp.y;
        if(f[x][y])continue;
        f[x][y]=1;
        cin>>str;
        for(int i=0; i<str.size()-1; i++)
        {
                if(str[i]=='R')     {graph[x+1][y]=1; if(!f[x+1][y]){ temp.x=x+1; temp.y=y; q.push(temp);} }
                else if(str[i]=='T'){graph[x][y+1]=1; if(!f[x][y+1]){ temp.x=x; temp.y=y+1; q.push(temp);} }
                else if(str[i]=='L'){graph[x-1][y]=1; if(!f[x-1][y]){ temp.x=x-1; temp.y=y; q.push(temp);} }
                else if(str[i]=='B'){graph[x][y-1]=1;if(!f[x][y-1]){ temp.x=x; temp.y=y-1; q.push(temp);} }
        }
        if(str[str.size()-1]=='.')break;
     }
     int cnt=0;
     for(int i=1; i<=10; i++)
     for(int j=1; j<=10; j++)
     if(graph[i][j])cnt++;
     cout<<cnt<<endl;
     for(int i=1; i<=10; i++)
     for(int j=1; j<=10; j++)
     if(graph[i][j])cout<<i<<' '<<j<<endl;   
}
 
int main()
{
    cin>>n;
    if(getchar()=='\n')
    {
    input(); 
    BFS1();
    }
    else BFS2();
    system("pause");
    return 0;
}

// by zhujf553
#include <iostream>
#include <string.h>
#include <string>
 
using namespace std;
 
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const char dc[4] = {'R', 'T', 'L', 'B'};
int dn[128];
 
string st;
bool smap[12][12];
int n, xx, yy;
int q[10000][2];
 
void work1()
{
	int i, j, k, x, y;
	for(i = 0 ; i < st.length() ; i++)
		n = n * 10 + st[i] - '0';
	int op = 0, cl = 1;
	int nx = 10000, ny = 10000;
	for(i = 1 ; i <= n ; i++)
	{
		cin >> x >> y;
		smap[x][y] = true;
		if(x < nx || (x == nx && y < ny))
			nx = x, ny = y;
	}
	q[0][0] = nx, q[0][1] = ny;
	smap[nx][ny] = false;
	cout << nx << ' ' << ny << endl;
	while(op < cl)
	{
		if(op != 0) cout << ",\n";
		nx = q[op][0], ny = q[op][1];
		for(k = 0 ; k <= 3 ; k++)
		if(smap[nx + dx[k]][ny + dy[k]])
		{
			smap[nx + dx[k]][ny + dy[k]] = false;
			q[cl][0] = nx + dx[k];
			q[cl][1] = ny + dy[k];
			cl++;
			cout << dc[k];
		}
		op++;
	}
	cout << ".\n";
}
 
void work2()
{
	dn['R'] = 0, dn['T'] = 1, dn['L'] = 2, dn['B'] = 3;
	int i, j, k, nx, ny;
	for(i = 0 ; i < st.length() ; i++)
	if(st[i] == ' ')break;
		else xx = xx * 10 + st[i] - '0';
	for(i++ ; i < st.length() ; i++)
		yy = yy * 10 + st[i] - '0';
	int op = 0, cl = 1;
	q[op][0] = xx, q[op][1] = yy;
	smap[xx][yy] = true;
	while(op < cl)
	{
		cin >> st;
		nx = q[op][0], ny = q[op][1];
		for(k = 0 ; k < st.length() - 1 ; k++)
		{
			j = dn[st[k]];
			smap[nx + dx[j]][ny + dy[j]] = true;
			q[cl][0] = nx + dx[j];
			q[cl][1] = ny + dy[j];
			cl++;
		}
		if(st[st.length() - 1] == '.') break;
		op++;
	}
	cout << cl << endl;
	for(i = 0 ; i <= 11 ; i++)
		for(j = 0 ; j <= 11 ; j++)
		if(smap[i][j])
			cout << i << ' ' << j << endl;
}
 
void work()
{
	getline(cin, st);
	if(st.find(" ") == -1)
		work1();
	else work2();
}
 
int main()
{
	work();
	return 0;
}