이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1e9+7;
const int MAX_N = 1e6;
const int MAX_N2 = 1e5;
const int TWO_MOD_INV = 500000004;
const int M = 998244353;
void solve() {
int h,w;
cin >> h >> w;
char grid[h][w];
for(int i=0; i<h; ++i) {
string s;
cin >> s;
for(int j=0; j<w; ++j) grid[i][j]=s[j];
}
int f[h][w], r[h][w];
memset(f, 0, sizeof f);
memset(r, 0, sizeof r);
int F=1, R=1;
queue<pair<int,int>>q;
q.push({0,0});
while(!q.empty()) {
int curx=q.front().first, cury=q.front().second;
q.pop();
if(grid[curx][cury]=='.') continue;
if(curx && f[curx-1][cury]) f[curx][cury]=f[curx-1][cury];
else if(cury && f[curx][cury-1]) f[curx][cury]=f[curx][cury-1];
else if(grid[curx][cury]=='F') {
f[curx][cury]=F;
++F;
}
if(curx && r[curx-1][cury]) r[curx][cury]=r[curx-1][cury];
else if(cury && r[curx][cury-1]) r[curx][cury]=r[curx][cury-1];
else if(grid[curx][cury]=='R') {
r[curx][cury]=R;
++R;
}
if(curx+1<h && ((f[curx][cury] && !f[curx+1][cury]) or (r[curx][cury] && !r[curx+1][cury]))) q.push({curx+1, cury});
if(cury+1<w && ((f[curx][cury] && !f[curx][cury+1]) or (r[curx][cury] && !r[curx][cury+1]))) q.push({curx, cury+1});
}
cout << F+R-2 << endl;
}
signed main()
{
//freopen("odometer.in","r",stdin);
//freopen("odometer.out","w",stdout);
int t=1;
while(t--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |