POJ 3083

- 日理万妓 2022-10-03 01:49 42阅读 0赞

#include <stdio.h>
    #include <memory.h>
    const int maxn=40+10;
    int visit[maxn*maxn];
    int map[maxn][maxn];
    int m,n;
    int dir[4][2]={
        {0,-1},{-1,0},{0,1},{1,0}};
    int step1;
    int step2;
    void dfs1(int step ,int way,int tem)
    {	
    	int x=tem/n;
    	int y=tem%n;
    	if(map[x][y]=='E'){
    		step1=step;
    		return ;
    	}
    	int k=(way+3)%4;
    	int ndir;
    	int dx,dy;
    	for(int j=0;j<4;j++)
    	{
    		ndir=(k+j)%4;
    		dx=x+dir[ndir][0];
    		dy=y+dir[ndir][1];
    		if(dx>=0&&dx<m&&dy>=0&&dy<n&&map[dx][dy]!='#'){
    			dfs1(step+1,ndir,dx*n+dy);
    			return ;
    		}
    		
        }
    }
    void dfs2(int step ,int way,int tem)
    {	
    	int x=tem/n;
    	int y=tem%n;
    	if(map[x][y]=='E') {
    		step2=step;
    		return ;
    	}
    	int k=(way+1)%4;
    	int ndir;
    	int dx,dy;
    	for(int j=0;j<4;j++)
    	{
    		ndir=(k-j+4)%4;
    		dx=x+dir[ndir][0];
    		dy=y+dir[ndir][1];
    		if(dx>=0&&dx<m&&dy>=0&&dy<n&&map[dx][dy]!='#')
    		{	 
    			dfs2(step+1,ndir,dx*n+dy);
    			return ;
    		}
    		
    	}
    }
    int bfs(int st,int fin)
    {
    	
    	int dis[maxn*maxn];
    	dis[st]=1;
    	int queue[maxn*maxn];
    	int font=0;
    	int rear=0;
    	visit[st]=1;
    	queue[rear++]=st;
    	while(font<rear)
    	{
    		int xy=queue[font++];
    		int x=xy/n;
    		int y=xy%n;
    		int dx,dy;
    		int dxy;
    		for(int i=0;i<4;i++)
    		{
    			dx=x+dir[i][0];
    			dy=y+dir[i][1];
    			dxy=dx*n+dy;
    			if(map[dx][dy]!='#'&&dx>=0&&dx<m&&dy>=0&&dy<n&&!visit[dxy])
    			{
    				visit[dxy]=1;
    				queue[rear++]=dxy;
    				dis[dxy]=dis[xy]+1;
    				if(dxy==fin) return dis[fin];
    			}
    			
    		}
    
    	}
    
    
    }
    int main()
    {
    	int N;
    	scanf("%d",&N);
    	while(N--)
    	{
    		step1=1;
    		step2=1;
    		memset(visit,0,sizeof(visit));
    		int st;
    		int fin;
    		scanf("%d %d",&n,&m);
    		int i,j;
    		int way;
    		for(i=0;i<m;i++)
    		{
    			getchar();
    			for(j=0;j<n;j++)
    			{
    				scanf("%c",&map[i][j]);
    				if(map[i][j]=='S'){ 
    					st=i*n+j;
    					if(i==0) way=3;
    					if(i==m-1) way=1;
    					if(j==0) way=2;
    					if(j==n-1) way=0;
    				}
    				if(map[i][j]=='E') fin=i*n+j;
    			}
    		}
    		dfs1(1,way,st);
    		dfs2(1,way,st);
    		printf("%d %d %d\n",step1,step2,bfs(st,fin));
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/lj-vs-lishimin/archive/2012/05/29/2774404.html