結果

問題 No.402 最も海から遠い場所
ユーザー horiesinitihoriesiniti
提出日時 2016-07-24 18:06:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 876 ms / 3,000 ms
コード長 1,519 bytes
コンパイル時間 675 ms
コンパイル使用メモリ 66,192 KB
実行使用メモリ 84,164 KB
最終ジャッジ日時 2024-11-06 15:57:18
合計ジャッジ時間 4,020 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
39,244 KB
testcase_01 AC 12 ms
40,400 KB
testcase_02 AC 12 ms
39,756 KB
testcase_03 AC 12 ms
38,856 KB
testcase_04 AC 12 ms
39,756 KB
testcase_05 AC 11 ms
40,144 KB
testcase_06 AC 12 ms
39,368 KB
testcase_07 AC 11 ms
40,400 KB
testcase_08 AC 12 ms
39,628 KB
testcase_09 AC 12 ms
39,376 KB
testcase_10 AC 12 ms
39,244 KB
testcase_11 AC 12 ms
39,624 KB
testcase_12 AC 11 ms
38,984 KB
testcase_13 AC 14 ms
39,500 KB
testcase_14 AC 14 ms
41,292 KB
testcase_15 AC 25 ms
42,316 KB
testcase_16 AC 35 ms
44,940 KB
testcase_17 AC 245 ms
63,124 KB
testcase_18 AC 876 ms
51,472 KB
testcase_19 AC 70 ms
47,632 KB
testcase_20 AC 585 ms
47,636 KB
testcase_21 AC 255 ms
84,164 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:31:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |         scanf("%d %d",&h,&w);
      |         ~~~~~^~~~~~~~~~~~~~~
main.cpp:34:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |                 scanf("%s",line[i]);
      |                 ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
int memo[3001][3001];
char line[3001][3001];
int dxs[8]={-1,-1,-1,0,0,1,1,1};
int dys[8]={-1,0,1,-1,1,-1,0,1};
int h,w;
struct E{
	int x,y;
};

int f(int p,int d,int max){
	int p1=p+d;
	if((0<=p1)&&(p1<max)){
		return p1;
	}
	if(p1<0){
		return 0;
	}
	return max-1;
}

std::queue<E> qu;

int main() {
	// your code goes here

	scanf("%d %d",&h,&w);
	memset(memo,0,sizeof(memo));
	for(int i=0;i<h;i++){
		scanf("%s",line[i]);
	}
	int ans=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if((i==0)||(i==h-1)||(j==0)||(j==w-1)){
				if(line[i][j]=='#'){
					E e1;
					e1.x=j;
					e1.y=i;
					qu.push(e1);
					memo[i][j]=1;
					ans=1;
				}
			}else if(line[i][j]=='#'){
				for(int k=0;k<8;k++){
					if(line[i+dys[k]][j+dxs[k]]=='.'){
						E e1;
						e1.x=j;
						e1.y=i;
						qu.push(e1);
						memo[i][j]=1;
						ans=1;
						break;
					}
				}
			}
		}
	}
	
	while(qu.empty()==false){
		std::queue<E> next;
		while(qu.empty()==false){
			E e1=qu.front();
			qu.pop();
			int x=e1.x;
			int y=e1.y;
			for(int i=0;i<8;i++)
			{
				int x1=f(x,dxs[i],w);
				int y1=f(y,dys[i],h);
				if((memo[y1][x1]==0)&&(line[y1][x1]=='#')){
					memo[y1][x1]=memo[y][x]+1;
					E e2;
					e2.y=y1;
					e2.x=x1;
					next.push(e2);
					if(ans<memo[y1][x1]){
						ans=memo[y1][x1];
					}
				}
			}
		}
		while(next.empty()==false)
		{
			qu.push(next.front());
			next.pop();
		}
	}
	printf("%d\n",ans);
	return 0;
}
0