比赛 练习赛 评测结果 AAATTTTTTTTTTTTA
题目名称 位图 最终得分 25
用户昵称 十二12 运行时间 12.003 s
代码语言 C++ 内存使用 13.97 MiB
提交时间 2019-05-23 15:50:49
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,a[500][500];
int dx[5]= {-1,0,1,0};
int dy[5]= {0,1,0,-1};
queue<int>q,t;
void bfs()
{
	while(!q.empty()) {
		int x=q.front();
		int y=t.front();
		q.pop();
		t.pop();
//	cout<<x<<" "<<y<<endl;;
		for(int i=0; i<4; i++) {
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&a[xx][yy]!=0) {
				if(a[xx][yy]==-1) {
					a[xx][yy]=a[x][y]+1;
 
					          q.push(xx);
					          t.push(yy);
					         // cout<<q.front()<<" "<<t.front()<<endl;;
				} else {
					if(a[xx][yy]>a[x][y]+1) {
						a[xx][yy]=a[x][y]+1;
						q.push(xx);
						t.push(yy);
					}
 
				}
			//	cout<<xx<<" "<<yy<<" "<<x<<" "<<y<<endl;
			}
 
		}
 
	}
}
int main()
{  freopen("bit.in","r",stdin);
  freopen("bit.out","w",stdout);
	memset(a,-1,sizeof(a));
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		string s;
		cin>>s;
		for(int j=0; j<s.length(); j++) {
			if(s[j]=='1') {
				a[i][j+1]=0;
				q.push(i);
				t.push(j+1);
			}
 
		}
	}
	bfs();
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++)
			cout<<a[i][j]<<" ";
		cout<<endl;
	}
 
 
 
 
}