結果

問題 No.157 2つの空洞
ユーザー omuomu
提出日時 2015-02-27 01:25:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,898 bytes
コンパイル時間 846 ms
コンパイル使用メモリ 90,792 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 22:06:28
合計ジャッジ時間 1,619 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 1 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,944 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 3 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int bfs(int, int)’:
main.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
   69 | }
      | ^

ソースコード

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))


int dx[4] = { 1,-1, 0, 0};
int dy[4] = { 0, 0, 1,-1};

const int Max = 21;

int w,h;
char c[Max][Max];
bool f[Max][Max];

typedef pair<int,int> P;

char mark[2] = {'a','b'};

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

	queue<P> q;
	q.push( P(i,j) );
	bool flag[Max][Max];
	CLR(flag);

	while(!q.empty())
	{
		
		P now = q.front();q.pop();
		int x = now.first,y = now.second;

		if(c[x][y] == mark[1])
		{
			return abs(x-i)+abs(y-j)-1;
		}

		for(int k = 0;k < 4;k++)
		{
			int tx = x+dx[k],ty = y+dy[k];

			if((tx >= 0 && ty >= 0 && tx < h && ty < w && !flag[tx][ty]))
			{
				flag[tx][ty] = true;
				q.push(P(tx,ty));
			}
		}
	} 
}

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++)
		{
			int tx = i+dx[k];int ty = j+dy[k];
			dfs(tx,ty,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++)
		{
			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];

	for(int i = 0;i < 2;i++)
	{
		CLR(f);
		cast(mark[i]);
	}

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

	cout << anser << endl;


	return 0;
}
0