結果

問題 No.157 2つの空洞
ユーザー omuomu
提出日時 2015-02-27 00:23:04
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,672 bytes
コンパイル時間 683 ms
コンパイル使用メモリ 85,308 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-23 21:54:34
合計ジャッジ時間 1,420 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>

using namespace std;

 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define MCLR(a) memset((a), -1 ,sizeof(a))



//遷移数
const int TMAX = 4;

//遷移変数
int dx[TMAX][2] = {{ 1, 0},
				   {-1, 0},
				   { 0, 1},
				   { 0,-1},};


int w,h;
char c[21][21];



bool f[21][21];//フラグ CLR(f);

int dfs2(int i,int j)
{
	if(i < 0 || j < 0 || i >= h || j >= w || f[i][j])return 0;
	f[i][j] = true;

	if(c[i][j] == 'b')
	{
		return 1;
	}else
	if(c[i][j] != 'a')
	{
		int Max = 0;
		for(int k = 0;k < 4;k++)
		{
			int tmp = dfs2(i+dx[k][0],j+dx[k][1])+1;
			if(tmp)tmp++;
			Max = max(Max,tmp);
		}
		return Max;
	}
	return 0;
}

int dfs(int i,int j,char ma)
{
	if(i < 0 || j < 0 || i >= h || j >= w || f[i][j])return 0;
	f[i][j] = true;

	if(c[i][j] == '#')return 0;
	
	if(c[i][j] == '.')
	{
		for(int k = 0;k < 4;k++)
		dfs(i+dx[k][0],j+dx[k][1],ma);
		c[i][j] = ma;
		return 1;
	}
	return 0;
}

void cast(char ma)
{
	for(int i = 0;i < h;i++)
		for(int j = 0;j < w;j++)
		{
			CLR(f);
			if(dfs(i,j,ma))return;
		}
}


int main()
{

	cin >> w >> h;

	for(int i = 0;i < h;i++)
		for(int j = 0;j < w;j++)
			cin >> c[i][j];
	cast('a');
	cast('b');

	int anser = 99999999;
	for(int i = 0;i < h;i++)
		for(int j = 0;j < w;j++)
		{
			CLR(f);
			if(c[i][j] == 'a')
			anser = min(dfs2(i,j),anser);
		}

	cout << anser << endl;


	return 0;
}
0