Submission #9501209

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int mod = 1e9 + 7;
int bfs2(vector<vector<int>> arr, pair<int, int> start_coordinates, int r, int c)
{
    queue<pair<int, int>> q; 
    q.push(start_coordinates);
    while (!q.empty()) 
    { 
        pair<int, int> t = q.front();
        q.pop(); 
        int start_r = t.fi;
        int start_c = t.se;
 
        if (start_r-1>=0)
        {
        	if (arr[start_r-1][start_c]==0 && (start_r-1!=start_coordinates.fi || start_c!=start_coordinates.se))
        	{
        		arr[start_r-1][start_c] = arr[start_r][start_c] + 1;
        		q.push(mp(start_r-1,start_c));
        	}
        }
        if (start_r+1<r)
        {
        	if (arr[start_r+1][start_c]==0 && ((start_r+1)!=start_coordinates.fi || start_c!=start_coordinates.se))
        	{
        		arr[start_r+1][start_c] = arr[start_r][start_c] + 1;
        		q.push(mp(start_r+1,start_c));
        	}
        }
        if (start_c-1>=0)
        {
        	if (arr[start_r][start_c-1]==0 && (start_r!=start_coordinates.fi || (start_c-1)!=start_coordinates.se))
        	{
        		arr[start_r][start_c-1] = arr[start_r][start_c] + 1;
        		q.push(mp(start_r,start_c-1));
        	}
        }
        if (start_c+1<c)
        {
        	if (arr[start_r][start_c+1]==0 && (start_r!=start_coordinates.fi || (start_c+1)!=start_coordinates.se))
        	{
        		arr[start_r][start_c+1] = arr[start_r][start_c] + 1;
        		q.push(mp(start_r,start_c+1));
        	}
        }
    } 
    int maxDis = 0;  
    for (int i = 0; i < r; ++i)
    {
     	for (int j = 0; j < c; ++j)
     	{
     		if (arr[i][j]==-1)
     		{
     			continue;
     		}
     		if (arr[i][j]>maxDis)
     		{
     			maxDis = arr[i][j];
     		}
     	}
    } 
    return maxDis;
}
int main()
{
	SPEED
	int c, r;
	cin >> r >> c;
	char ch;
	vector<vector<int>> labyrinth(r,vector<int>(c,0));
	int start_r, start_c;
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			cin >> ch;
			if (ch=='#')
			{
				labyrinth[i][j] = -1;
				
			}
		}
	}
	int ans = 0;


	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (labyrinth[i][j]==0)
			{
				//cout << "enter process\n";
				pair<int, int> t1 = mp(i,j);
				int t2 = bfs2(labyrinth,t1,r,c);
				//cout << t2 << '\n';
				ans = max(ans, t2);

			}
		}
	}

	cout << ans;
	return 0;
}

Submission Info

Judge Result