记录编号 |
363921 |
评测结果 |
AAAAAAAAAAAAAAAA |
题目名称 |
[POI 1999] 位图 |
最终得分 |
100 |
用户昵称 |
kZime |
是否通过 |
通过 |
代码语言 |
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();
}