一次AC，太给力了！一开始被这种很不习惯的数学坐标系给弄晕了，长期用的都是数组表示坐标。后来想想其实不需要关注于坐标系怎样放置，关心R/T/L/B这四个方向，对应的X/Y如何变换即可。
除此之外，注意到处理的时候进队列的顺序是一样的。
以下是我的代码：
#include<iostream>
#include<string>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 10;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const char sp[]={'R','T','L','B'};
struct point
{
int x,y;
};
string first_line;
int n,fx,fy;
bool graph[maxn+1][maxn+1];
void condition_1()
{
fx=fy=0;
memset(graph,false,(maxn+1)*(maxn+1)*sizeof(bool));
for(int i=1;i<=n;i++)
{
int ta,tb;
cin>>ta>>tb;
if(fx==0&&fy==0)
{fx=ta;fy=tb;}
graph[ta][tb]=true;
}
int cnt=0;;
queue<point> q;
string ans[120];
point newp={fx,fy};
q.push(newp);
graph[newp.x][newp.y]=false;
while(!q.empty())
{
point p=q.front();q.pop();
cnt++;
for(int k=0;k<4;k++)
{
newp.x=p.x+dx[k];
newp.y=p.y+dy[k];
if(newp.x>=1&&newp.x<=maxn&&newp.y>=1&&newp.y<=maxn&&graph[newp.x][newp.y])
{
ans[cnt]+=sp[k];
q.push(newp);
graph[newp.x][newp.y]=false;
}
}
if(cnt!=n)
ans[cnt]+=',';
else ans[cnt]+='.';
}
cout<<fx<<" "<<fy<<endl;
for(int i=1;i<=cnt;i++)
cout<<ans[i]<<endl;
}
void condition_2()
{
n=0;
memset(graph,false,(maxn+1)*(maxn+1)*sizeof(bool));
string newline;
queue<point> q;
point newp={fx,fy};
q.push(newp);n++;
graph[newp.x][newp.y]=true;
while(getline(cin,newline))
{
point p=q.front();q.pop();
for(string::size_type i=0;i<newline.size()-1;i++)
{
switch(newline[i])
{
case 'R':
newp.x=p.x+dx[0];
newp.y=p.y+dy[0];
break;
case 'T':
newp.x=p.x+dx[1];
newp.y=p.y+dy[1];
break;
case 'L':
newp.x=p.x+dx[2];
newp.y=p.y+dy[2];
break;
case 'B':
newp.x=p.x+dx[3];
newp.y=p.y+dy[3];
}
if(newp.x>=1&&newp.x<=maxn&&newp.y>=1&&newp.y<=maxn)
{
q.push(newp);n++;
graph[newp.x][newp.y]=true;
}
}
}
cout<<n<<endl;
for(int i=1;i<=maxn;i++)
for(int j=1;j<=maxn;j++)
if(graph[i][j])
cout<<i<<" "<<j<<endl;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
getline(cin,first_line);
if(sscanf(first_line.c_str(),"%d%d",&fx,&fy)!=2)
{
sscanf(first_line.c_str(),"%d",&n);
condition_1();
}
else
condition_2();
return 0;
}
posted on 2011-02-21 11:31
lee1r 阅读(219)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：基础/模拟