一次AC，太給力了！一開始被這種很不習慣的數(shù)學坐標系給弄暈了，長期用的都是數(shù)組表示坐標。后來想想其實不需要關注于坐標系怎樣放置，關心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 閱讀(250)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：基礎/模擬