1 条题解

  • 0
    @ 2023-9-10 15:09:40
    #include<bits/stdc++.h>
    #define inf 999999999
    #define ll long long
    using namespace std;
    struct point
    {
    	int x,y;
    	friend bool operator == (point a,point b){
    		return (a.x==b.x && a.y==b.y);
    	}
    };
    struct node
    {
    	char way;
    	int num;
    };
    point s,e;
    int n,m;
    int a[110][110];
    int dis[110][110];
    queue<point>q;
    int tox[4]={-1,0,1,0};
    int toy[4]={0,1,0,-1};
    deque<node>ans;
    int main()
    {
    	scanf("%d%d\n",&n,&m);
    	n=n*2-1;
    	m=m*2-1;
    	for(int i=1; i<=n; i++)
    	{
    		for(int j=1; j<=m; j++)
    		{
    			dis[i][j]=-1;
    			char c;
    			c=getchar();
    			if(c=='.')continue;
    			else if(c=='+')a[i][j]=2;
    			else if(c=='S')s.x=i,s.y=j,a[i][j]=2;
    			else if(c=='E')e.x=i,e.y=j,a[i][j]=2;
    			else a[i][j]=1;
    		}getchar();
    	}
    	dis[s.x][s.y]=0;
    	point t;
    	t=s;
    	q.push(t);
    	while(!q.empty())
    	{
    		t=q.front();
    		q.pop();
    		if(t==e)break;
    		for(int i=0; i<4; i++)
    		{
    			point t1=t;
    			t1.x+=tox[i];
    			t1.y+=toy[i];
    			if(t1.x<1 || t1.x>n || t1.y<1 || t1.y>m || a[t1.x][t1.y]==0 || dis[t1.x][t1.y]!=-1)continue;
    			dis[t1.x][t1.y]=dis[t.x][t.y]+1;
    			q.push(t1);
    		}
    	}
    	int last=-1;
    	int sum=0;
    	t=e;
    	while(1)
    	{
    		if(t==s)
    		{
    			node tt;
    			if(last==0)tt.way='S';
    			if(last==1)tt.way='W';
    			if(last==2)tt.way='N';
    			if(last==3)tt.way='E';
    			tt.num=sum;
    			ans.push_front(tt);
    			break;
    		}
    		int to;
    		if(a[t.x][t.y]==2)sum++;
    		for(int i=0; i<4; i++)
    		{
    			point t1=t;
    			t1.x+=tox[i];
    			t1.y+=toy[i];
    			if(t1.x<1 || t1.x>n || t1.y<1 || t1.y>m || a[t1.x][t1.y]==0 || dis[t1.x][t1.y]!=dis[t.x][t.y]-1)continue;
    			to=i;
    			break;
    		}
    		if(last!=to)
    		{
    			if(last!=-1)
    			{
    				node tt;
    				if(last==0)tt.way='S';
    				if(last==1)tt.way='W';
    				if(last==2)tt.way='N';
    				if(last==3)tt.way='E';
    				tt.num=sum-1;
    				ans.push_front(tt);
    				sum=1;
    			}
    			last=to;
    		}
    		t.x+=tox[to];
    		t.y+=toy[to];
    	}
    	for(int i=0; i<ans.size(); i++)
    	{
    		printf("%c %d\n",ans[i].way,ans[i].num);
    	}
    	
    	return 0;
    }
    
    • 1

    [Usaco2005 Open]Navigating the City 城市交通

    信息

    ID
    1687
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者