2019-05-05 05:05:13 C++

C++

Copy Copied! Full
#include <iostream> using namespace std; #define QUEUE_SIZE 1000002 #define next(a) (((a)+1)%QUEUE_SIZE) int queue[QUEUE_SIZE]; int front,rear; void enqueue(int x){ if(next(rear)==front){ exit(1); } queue[rear]=x; rear = next(rear); } int dequeue(){ if(front==rear){ exit(1); } int x = queue[front]; front = next(front); return x; } int isempty(){ return front==rear; } void init(){ front = rear = 0; } int black[1000001]; int score[1001][1001]; int main(void){ int H,W; int bc=0; cin >> H >> W; string s[H]; for(int i=0;i<H;i++){ cin >> s[i]; } //初期の黒い点の座標を保存する for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(s[i][j]=='#'){ black[bc]=100000*i+j; bc++; } } } //各黒い点について幅優先探索 bfs for(int i=0;i<bc;i++){ int temp = black[i]; int x = temp/100000; int y = temp%100000; score[x][y]=0; //x y から幅優先探索していく init(); enqueue(x*100000+y); while(isempty==0){ int temp = dequeue(); int x = temp/100000; int y = temp%100000; for(int i=0;i<4;i++){ int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; if(score[x+dx[i]][y+dy[i]]==0 ||score[x+dx[i]][y+dy[i]]>score[x][y]+1){ score[x+dx[i]][y+dy[i]] = score[x][y]+1; enqueue((x+dx[i])*100000+y+dy[i]); } } } } int ans = 0; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ cout << score[i][j]; } cout << endl; } cout << ans; }
RECOMMEND