P2499 迷宫 😕

1 comments

  • @ 2025-6-22 1:14:29

    深度优先搜索 DFS

    #include <bits/stdc++.h>
    using namespace std;
    int k, n, s1, s2, e1, e2, vis[105][105];
    char maps[105][105];
    
    int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
    
    bool dfs(int x, int y) {
    	vis[x][y] = 1;
    	int tx, ty;
    	if (x == e1 && y == e2)
    		return true;
    	for (int i = 0; i < 4; i++) {
    		tx = x + dx[i], ty = y + dy[i];
    		if (tx >= 0 && tx < n && ty >= 0 && ty < n && maps[tx][ty] != '#' && vis[tx][ty] == 0)
    			if (dfs(tx, ty))
    				return true;
    	}
    	return false;
    }
    
    int main() {
    	cin >> k;
    	for (int i = 0; i < k; i++) {
    		cin >> n;
    		for(int i=0;i<105;i++)
    			for(int j=0;j<105;j++)
    				vis[i][j]=0;
    		for (int i = 0; i < n; i++)
    			for (int j = 0; j < n; j++)
    				cin >> maps[i][j];
    		cin >> s1 >> s2 >> e1 >> e2;
    		if (dfs(s1, s2))
    			cout << "YES\n";
    		else
    			cout << "NO\n";
    	}
    	return 0;
    }
    

    广度优先搜索 BFS

    #include <bits/stdc++.h>
    using namespace std;
    #define in cin
    #define out cout
    char maps[105][105];
    int n, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1};
    struct node {
    	int x, y;
    };
    queue<node> q;
    bool bfs(int sx, int sy, int ex, int ey) {
    	while (!q.empty())
    		q.pop();
    	maps[sx][sy] = '#', q.push({sx, sy});
    	while (!q.empty()) {
    		int ux = q.front().x, uy = q.front().y;
    		q.pop();
    		if (ux == ex && uy == ey)
    			return true;
    		for (int i = 0; i < 4; i++) {
    			int tx = dx[i] + ux, ty = uy + dy[i];
    			if (tx >= 0 && ty >= 0 && tx < n && ty < n && maps[tx][ty] == '.')
    				maps[tx][ty] = '#', q.push({tx, ty});
    		}
    	}
    	return false;
    }
    int main() {
    	int t;
    	in >> t;
    	while (t--) {
    		in >> n;
    		for (int i = 0; i < n; i++)
    			for (int j = 0; j < n; j++)
    				in >> maps[i][j];
    		int sx, sy, ex, ey;
    		in >> sx >> sy >> ex >> ey;
    		if (bfs(sx, sy, ex, ey))
    			out << "YES\n";
    		else
    			out << "NO\n";
    	}
    	return 0;
    }
    

    动态规划 DP/图论 最短路-Floyd

    #include <bits/stdc++.h>
    using namespace std;
    #define in cin
    #define out cout
    char maps[105][105];
    int n, dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1}, dp[105][105];
    
    int main() {
    	int t;
    	in >> t;
    	while (t--) {
    		in >> n;
    		for (int i = 0; i < n; i++)
    			for (int j = 0; j < n; j++)
    				in >> maps[i][j];
    		memset(dp, 0, sizeof(dp));
    		int sx, sy, ex, ey;
    		in >> sx >> sy >> ex >> ey;
    		dp[sx][sy] = 1;
    		for (int k = 0; k < n * n; k++)
    			for (int i = 0; i < n; i++)
    				for (int j = 0; j < n; j++)
    					if (maps[i][j] == '.')
    						for (int l = 0; l < 4; l++) {
    							int tx = dx[l] + i, ty = dy[l] + j;
    							if (tx >= 0 && ty >= 0 && tx < n && ty < n && maps[tx][ty] == '.')
    								dp[i][j] = max(dp[i][j], dp[tx][ty]);
    						}
    		if (dp[ex][ey])
    			out << "YES\n";
    		else
    			out << "NO\n";
    	}
    	return 0;
    }
    
    • 1

    Information

    ID
    2499
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    # Submissions
    133
    Accepted
    14
    Uploaded By