记录编号 363921 评测结果 AAAAAAAAAAAAAAAA
题目名称 [POI 1999] 位图 最终得分 100
用户昵称 GravatarkZime 是否通过 通过
代码语言 C++ 运行时间 0.069 s
提交时间 2017-01-14 11:32:03 内存使用 0.57 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int m,n,map[33125],f[33125];
queue<int> bfs;
void read(){
	memset(f,127,sizeof(f));
	cin>>n>>m;
	getchar();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int c=getchar()-48,d=(i-1)*m+j;
			map[d]=c;
			if(c==1){
				f[d]=0;
				bfs.push(d);
			}
		}
		getchar();
	}
}
void solve(){
	int w[4]={-1*m,-1,+1,m};
	while(!bfs.empty()){
		int d=bfs.front();
		bfs.pop() ;
		int x=d%m==0?d/m:d/m+1;//d的纵坐标 
		int y=(d+m)%(x*m);//表示d的横坐标 
		if(!y)y=m;
		for(int i=0;i<=3;i++){
			if(x==1&&i==0||x==n&&i==3||y==1&&i==1||y==m&&i==2)continue;
			int c=d+w[i];
			if(c>m*n||c<1)continue;
				if(f[c]>f[d]+1){
					f[c]=f[d]+1;
					bfs.push(c);
				}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cout<<f[(i-1)*m+j]<<" ";
		}
		cout<<endl;
	}
}
int main(){
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout);
	read();
	solve();
}