1 条题解

  • 0
    @ 2022-10-2 15:16:00
    #pragma GCC optimize(3,"Ofast","inline")
    #include <bits/stdc++.h>
    using namespace std;
    inline int read()
    {
    	char ch=getchar();
    	int x=0,m=1;
    	while(!isdigit(ch)){
    		if (ch=='-') m=-1;
    		ch=getchar();
    	}
    	while(isdigit(ch)){
    		x=x*10+ch-'0';
    		ch=getchar();
    	}
    	return x*m;
    }
    inline void write(int x)
    {
    	if (x<0) putchar('-'),x=-x;
    	if (x>9) write(x/10);
    	putchar(x%10+'0');
    }
    int n,m;
    struct Node{
    	int x,y,z;
    }f[10010];
    short dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
    bool p[110][110];
    inline int bfs(int x1,int y1,int x,int y)
    {
    	int h(0),t(1);
    	f[1].x=x1;f[1].y=y1;
    	while(h<t){
    		++h;
    		if (f[h].x==x&&f[h].y==y) return f[h].z;
    		for (int i=1;i<=4;i++){
    			int xx(dx[i]+f[h].x),yy(dy[i]+f[h].y);
    			if (p[xx][yy]==false) continue;
    			f[++t].x=xx;
    			f[t].y=yy;
    			f[t].z=f[h].z+1;
    		}
    	}
    	return -1;
    }
    signed main()
    {
    	n=read(),m=read();
    	char ch(getchar());
    	int x1,y1,x2,y2;
    	for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){
    		while(ch!='S'&&ch!='T'&&ch!='.'&&ch!='#') ch=getchar();
    		if (ch=='S') x1=i,y1=j,p[i][j]=true;
    		else if (ch=='T') x2=i,y2=j,p[i][j]=true;
    		else if (ch=='.') p[i][j]=true;
    		ch=getchar();
    	}
    	write(bfs(x1,y1,x2,y2));
    	return 0;
    }
    
    • 1

    信息

    ID
    173
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    51
    已通过
    33
    上传者