搜索

P1605 迷宫

BFS模板题，到每个点判断一下是否有障碍物即可

#include<bits/stdc++.h>
using namespace std;
int n , m , t;
struct node{
	int x , y ;
}  a , b;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
bool v[1002][1002]; 
int ans ;
int s[1002][1002];
int in(int x, int y){
	return 1 <= x && x <= n && 1 <= y && y <= m ;
}
int k[1000002];
void dfs(int x ,int y){
	if((x == b.x) && (y == b.y)){
			ans ++ ;
		return ;
	}
	for(int i = 0 ; i < 4 ;i ++){
		int nx = dx[i] + x;
		int ny = dy[i] + y;
		if(in(nx , ny) && !v[nx][ny] && !s[nx][ny]) {
			v[x][y] = 1;
			v[nx][ny] = 1;
			dfs(nx , ny );
			v[x][y] = 0;
			v[nx][ny] = 0;
		} 
	}
	return ;
}
int main () {
	cin >> n >> m >> t;
	cin >> a.x >> a.y >> b.x >> b.y ;
	for(int i = 1; i <= t ; i ++){
          int x , y;
          cin >> x >> y;
          s[x][y] = 1;
	}
	v[a.x][a.y] = 1 ; 
	dfs(a.x , a.y);
	cout << ans << endl;
} 

P1443 马的遍历

BFS，注意马的四个方向，用二维数组存储距离

#include<bits/stdc++.h>
using namespace std;
int n , m , s , p;
int in(int x,int y){
	return 1 <= x && x <= n && 1 <= y && y <= m ;
}
queue<int> q;
int d[1002][1002];
int dx[] = {1 , 1 , 2 ,  2 , -1 , -1 , -2 , -2 };
int dy[] = {2 , -2 , 1 , -1,  2 , -2 , 1 , -1};
int v[1002][1002];
void bfs(){
	memset(d , -1 ,sizeof d);
	d[s][p] = 0; 
	while(q.size()){
	int x = q.front();
	q.pop();
	int y = q.front();
	q.pop();
	if(v[x][y])continue;
	v[x][y] = 1;
	for(int i = 0 ; i < 8 ;i ++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(in(nx , ny)  && d[nx][ny] == -1 && !v[nx][ny]){
			q.push(nx) , q.push(ny) ;
			d[nx][ny] = d[x][y] + 1;
		}
	}	
	}
}
int main () {
	cin >> n >> m >> s >> p;
	q.push(s) ;
	q.push(p) ;
	bfs();
	for(int i = 1; i <= n ; i ++){
		for(int j = 1; j <= m ;j ++){
			cout << d[i][j] << " ";
		}
		cout << endl;
	}
}