7 solutions

  • 1
    @ 2024-3-15 22:07:12
    #include<iostream>
    using namespace std;
    void dfs(int x, int y);
    bool check(int nx, int ny);
    int n, mp[105][105], ha, la, hb, lb;
    bool vis[105][105] = {}, flag = false;
    int main()
    {
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= n; j++)
    			cin >> mp[i][j];
    	cin >> ha >> la >> hb >> lb;
    	if (mp[ha][la] == 1)
    	{
    		cout << "NO" << endl;
    		return 0;
    	}
    	dfs(ha, la);
    	if (flag)
    		cout << "YES" << endl;
    	else cout << "NO" << endl;
    	return 0;
    }
    void dfs(int x, int y)
    {
    	int dx[4] = { 0,0,1,-1 };
    	int dy[4] = { 1,-1,0,0 };
    	int nx, ny;
    	if (vis[x][y] || flag)
    		return;
    	vis[x][y] = true;
    	if (x == hb && y == lb)
    	{
    		flag = true;
    		return;
    	}
    	for (int i = 0; i < 4; i++)
    	{
    		nx = x + dx[i];
    		ny = y + dy[i];
    		if (check(nx,ny))
    			dfs(nx, ny);
    	}
    }
    bool check(int nx,int ny)
    {
    	if (nx > 0 && nx <= n && ny > 0 && ny <= n && vis[nx][ny] == false && mp[nx][ny] == 0)
    		return true;
    	return false;
    }
    

    Information

    ID
    767
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    8
    Tags
    # Submissions
    922
    Accepted
    163
    Uploaded By