結果

問題 No.402 最も海から遠い場所
ユーザー horiesinitihoriesiniti
提出日時 2016-07-24 18:05:47
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,494 bytes
コンパイル時間 603 ms
コンパイル使用メモリ 65,256 KB
実行使用メモリ 84,292 KB
最終ジャッジ日時 2024-11-06 15:57:13
合計ジャッジ時間 4,064 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
38,992 KB
testcase_01 AC 12 ms
40,140 KB
testcase_02 AC 12 ms
39,884 KB
testcase_03 WA -
testcase_04 AC 12 ms
40,012 KB
testcase_05 AC 11 ms
39,500 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 12 ms
39,756 KB
testcase_11 AC 12 ms
39,112 KB
testcase_12 AC 12 ms
40,908 KB
testcase_13 AC 14 ms
40,264 KB
testcase_14 AC 13 ms
40,652 KB
testcase_15 AC 26 ms
42,188 KB
testcase_16 AC 34 ms
43,024 KB
testcase_17 AC 243 ms
62,956 KB
testcase_18 AC 858 ms
51,472 KB
testcase_19 WA -
testcase_20 AC 578 ms
47,760 KB
testcase_21 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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]);
	}
	
	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;
				}
			}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;
						break;
					}
				}
			}
		}
	}
	int ans=0;
	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