4 条题解

  • 0
    @ 2023-4-1 9:18:13
    #include
    using namespace std;
    int r,c,dx[]= {-1,0,0,1},dy[]= {0,-1,1,0};
    char a[45][45];
    bool vis[45][45];
    struct Point {
    	int x,y,step;
    };
    queue<Point> q;
    bool check(int x,int y) { // 检查该点(x,y)是否可以通行以及是否未走过
    	return x>=1&&y>=1&&x<=r&&y<=c&&!vis[x][y]&&a[x][y]=='.';
    }
    int bfs() {
    	vis[1][1]=1;
    	q.push((Point) {
    		1,1,1
    	}); // 点(1,1)为什么花了1步我不理解,0步是WA,1步是AC
    	while(q.size()) {
    		Point now=q.front();
    		q.pop();
    		for(short i=0; i<4; i++) {
    			int nx=now.x+dx[i],ny=now.y+dy[i];
    			if(check(nx,ny)) {
    				if(nx==r&&ny==c)return now.step+1;
    				vis[nx][ny]=1;
    				q.push((Point) {
    					nx,ny,now.step+1
    				});
    			}
    		}
    	}
    }
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	cin>>r>>c;
    	for(int i=1; i<=r; i++)
    		for(int j=1; j<=c; j++)
    			cin>>a[i][j];
    	cout<<bfs();
    	return 0;
    }
    

    信息

    ID
    993
    时间
    1000ms
    内存
    64MiB
    难度
    3
    标签
    递交数
    49
    已通过
    27
    上传者