1 条题解

  • 0
    @ 2023-3-17 20:42:12
    #include <bits/stdc++.h>
    using namespace std;
    const int N = 1005;
    typedef pair<int,int> PII;
    int g[N][N],n;
    bool vis[N][N];
    int xq,yq,xz,yz;
    
    string t_s(int x,int y)
    {
    	return to_string(x)+to_string(y);
    }
    
    int bfs(int a,int b)
    {
    	unordered_map<string,int> h;
    	queue<string> q;
    	q.push(t_s(a,b));
    	h[t_s(a,b)] = 0;
    	while(!q.empty())
    	{
    		int tx[] = {1,-1,0,0},ty[] = {0,0,-1,1};
    		auto t = q.front();
    		q.pop();
    		int x = stoi(t[0]),y = stoi(t[1]);
    		int dis = h[t];
    		vis[x][y] = false;
    		if(x == xz && y == yz) return dis;
    		for(int i=0;i<4;i++)
    		{
    			int rx = x+tx[i],ry = y+ty[i];
    			if(rx>=1 && rx<=n && ry>=1 && ry<=n && vis[rx][ry] && g[rx][ry] == 0)
    			{
    				g[rx][ry] = 1;
    				q.push(t_s(rx,ry));
    				h[t] = dis+1;
    			}
    		}
    	}
    	return -1;
    }
    
    int main()
    {
    	cin >> n;
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    			cin >> g[i][j];
    	cin >> xq >> yq >> xz >> yz;
    	cout << bfs(xq,yq);
    	return 0;
    }
    
    • 1

    信息

    ID
    346
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    6
    已通过
    1
    上传者