题目

墙与门

给定一个网格，其中0表示门，-1表示墙，2147483647表示空房间。求每个空房间到最近门的距离，将结果填回网格。

输入格式:一个mxn的网格，0=门，-1=墙，2147483647=空房间
输出格式:将每个空房间替换为到最近门的距离
测试用例:

输入

2 2

0 -1

2147483647 2147483647

输出

0 -1

1 2

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,v;
};
queue<node> q;
int a[1010][1010];
int b[1010][1010];
int n,m;

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void bfs();

int main()
{
	
	cin>>n>>m;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]==-1) b[i][j] = -1;
			if(a[i][j]==0)
			{
				q.push({i,j,0});
				b[i][j] = 0;
			}
		}
	}
	
	bfs();
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}
void bfs()
{
	while(q.size()!=0)
	{
		node head = q.front();
		q.pop();
		for(int i = 0;i<4;i++)
		{
			int tx = head.x+dx[i];
			int ty = head.y+dy[i];
			if(tx>=0&&tx<n&&ty>=0&&ty<m&&a[tx][ty]==2147483647&&b[tx][ty]<=0)
			{
				b[tx][ty] = head.v+1;
				q.push({tx,ty,b[tx][ty]});
			}
		}
	}
}

地图中的最短距离

给定一个字符网格，S’表示起点(可能有多个)，表示可通行，'#表示障碍物。求每个可通行格子到最近'S'的最短距离。输入格式:第一行n,m;接下来n行字符串，含'S''#输出格式:n行，每行m个整数，表示距离(-1表示不可达)
测试用例:

输入:

3 5
S.#..
.#.#.
..#S.
输出:

0 1 -1 4 3

1 -1 0 -1 2

2 3 -1 0 1

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,v;
};
queue<node> q;
char a[1010][1010];
int b[1010][1010];
int n,m;

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void bfs();

int main()
{
	
	cin>>n>>m;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='#') b[i][j] = -1;
			if(a[i][j]=='S')
			{
				q.push({i,j,0});
				b[i][j] = 0;
			}
		}
	}
	
	bfs();
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}
void bfs()
{
	while(q.size()!=0)
	{
		node head = q.front();
		q.pop();
		for(int i = 0;i<4;i++)
		{
			int tx = head.x+dx[i];
			int ty = head.y+dy[i];
			if(tx>=0&&tx<n&&ty>=0&&ty<m&&a[tx][ty]=='.'&&b[tx][ty]<=0)
			{
				b[tx][ty] = head.v+1;
				q.push({tx,ty,b[tx][ty]});
			}
		}
	}
}

多起点迷宫最短路径

有一个NxM的迷宫，可走，'#’是墙。迷宫中有K个出口(K≥1)。求每个格子到最近出口的最短距离。

输入格式:第一行N,M,K;接下来N行迷宫;接下来K行每行xy表示出口坐标(1-based)
输出格式:N行M列，每个格子到最近出口的距离(

-1表示不可达)

测试用例:
输入:
3 4 2

....

.##.

....

1 1
3 4
输出:
0 1 2 2
1 -1 -1 1
2 2 1 0

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,v;
};
queue<node> q;
char a[1010][1010];
int b[1010][1010];
int n,m,k;

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void bfs();

int main()
{
	
	cin>>n>>m>>k;
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='#') b[i][j] = -1;
		}
	}
	for(int i = 0;i<k;i++)
	{
		int xx,yy;
		cin>>xx>>yy;
		q.push({xx-1,yy-1,0});
		b[xx-1][yy-1] = 0;
		a[xx-1][yy-1] = '/';
	}
	
	bfs();
	
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<m;j++)
		{
			cout<<b[i][j]<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}
void bfs()
{
	while(q.size()!=0)
	{
		node head = q.front();
		q.pop();
		for(int i = 0;i<4;i++)
		{
			int tx = head.x+dx[i];
			int ty = head.y+dy[i];
			if(tx>=0&&tx<n&&ty>=0&&ty<m&&a[tx][ty]=='.'&&b[tx][ty]<=0)
			{
				b[tx][ty] = head.v+1;
				q.push({tx,ty,b[tx][ty]});
			}
		}
	}
}