Submission #1120331

#TimeUsernameProblemLanguageResultExecution timeMemory
1120331vjudge1Tracks in the Snow (BOI13_tracks)C++17
2.19 / 100
1741 ms1036932 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld double


const int INF = 1e18;
const int mod = 12345;
const int sz = 4e3 + 5;

int n , m;
char a[sz][sz];
bool vis[sz][sz];
int dx[4] = {1 , -1 , 0 , 0};
int dy[4] = {0 , 0 , 1 , -1};

bool can_go(int x , int y)
{
    if(x >= 1 && n >= x && y >= 1 && m >= y && !vis[x][y] && a[x][y] != '.') return true;
    else return false;
}

void dfs(int x , int y)
{
    for(int i = 0;i < 4;i++)
    {
        if(can_go(x + dx[i] , y + dy[i]))
        {
            vis[x + dx[i]][y + dy[i]] = 1;
            dfs(x + dx[i] , y + dy[i]);
        }
    }
}

signed main()
{
   ios_base::sync_with_stdio(0);cin.tie(0);
   cin >> n >> m;
   int cnt = 0;
   for(int i = 1;i <= n;i++)
   {
       for(int j = 1;j <= m;j++)
       {
           cin >> a[i][j];
           if(a[i][j] == 'F') cnt++;
       }
   }
   int ans = 0;
   while(1)
   {
       int ansc = ans;
       for(int i = 1;i <= n;i++)
       {
           for(int j = 1;j <= m;j++)
           {
               if(!vis[i][j] && (a[i][j] == 'R'))
               {
                   vis[i][j] = 1;
                   dfs(i , j);
                   ans++;
               }
           }
       }
       for(int i = 1;i <= n;i++)
       {
           for(int j = 1;j <= m;j++)
           {
               if(!vis[i][j] && (a[i][j] == 'F'))
               {
                   vis[i][j] = 1;
                   dfs(i , j);
                   ans++;
               }
           }
       }
       if(ans == ansc) break;
   }
   if(cnt) ans++;
   cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...