Submission #1120331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120331		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	1741 ms	1036932 KiB

tracks

#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;
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70