CF1391B-Fix You
题目:
题目描述:
Consider a conveyor belt represented using a grid consisting of $ n $ rows and $ m $ columns. The cell in the $ i $ -th row from the top and the $ j $ -th column from the left is labelled $ (i,j) $ .
Every cell, except $ (n,m) $ , has a direction R (Right) or D (Down) assigned to it. If the cell $ (i,j) $ is assigned direction R, any luggage kept on that will move to the cell $ (i,j+1) $ . Similarly, if the cell $ (i,j) $ is assigned direction D, any luggage kept on that will move to the cell $ (i+1,j) $ . If at any moment, the luggage moves out of the grid, it is considered to be lost.
There is a counter at the cell $ (n,m) $ from where all luggage is picked. A conveyor belt is called functional if and only if any luggage reaches the counter regardless of which cell it is placed in initially. More formally, for every cell $ (i,j) $ , any luggage placed in this cell should eventually end up in the cell $ (n,m) $ .
This may not hold initially; you are, however, allowed to change the directions of some cells to make the conveyor belt functional. Please determine the minimum amount of cells you have to change.
Please note that it is always possible to make any conveyor belt functional by changing the directions of some set of cells.
输入格式:
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10 $ ). Description of the test cases follows.
The first line of each test case contains two integers $ n, m $ ( $ 1 \le n \le 100 $ , $ 1 \le m \le 100 $ ) — the number of rows and columns, respectively.
The following $ n $ lines each contain $ m $ characters. The $ j $ -th character in the $ i $ -th line, $ a_{i,j} $ is the initial direction of the cell $ (i, j) $ . Please note that $ a_{n,m}= $ C.
输出格式:
For each case, output in a new line the minimum number of cells that you have to change to make the conveyor belt functional.
样例:
样例输入 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 4
3 3
RRD
DDR
RRC
1 4
DDDC
6 9
RDDDDDRRR
RRDDRRDDD
RRDRDRRDR
DDDDRDDRR
DRRDRDDDR
DDRDRRDDC
1 1
C
|
样例输出 1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
| /*
*User: ybw051114
*Time: 2020.08.09 22:35:06
*/
#include <bits/stdc++.h>
using namespace std;
#ifndef use_ios11
#define use_ios11
using namespace std;
struct ins
{
int ans;
ins() { ans = 1; }
#define endl '\n'
void read()
{
}
void read1(char &s)
{
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
s = c;
if (c == EOF)
ans = 0;
}
void read1(string &s)
{
s = "";
char c = getchar();
for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
;
for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
s += c;
if (c == EOF)
ans = 0;
}
template <typename T>
void read1(T &n)
{
T x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-')
f = -1;
if (c == EOF)
{
ans = 0;
return;
}
}
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
n = x * f;
if (c == EOF)
ans = 0;
if (c != '.')
return;
T l = 0.1;
while ((c = getchar()) <= '9' && c >= '0')
x = x + (c & 15) * l, l *= 0.1;
n = x * f;
if (c == EOF)
ans = 0;
}
void write() {}
void write1(string s)
{
int n = s.size();
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(const char *s)
{
int n = strlen(s);
for (int i = 0; i < n; i++)
putchar(s[i]);
}
void write1(char s) { putchar(s); }
void write1(float s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%df", x);
printf(y, s);
}
void write1(double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dlf", x);
printf(y, s);
}
void write1(long double s, int x = 6)
{
char y[10001];
sprintf(y, "%%.%dLf", x);
printf(y, s);
}
template <typename T>
void write1(T n)
{
if (n < 0)
n = -n, putchar('-');
if (n > 9)
write1(n / 10);
putchar('0' + n % 10);
}
template <typename T>
friend ins operator>>(ins x, T &n);
template <typename T>
friend ins operator<<(ins x, T n);
operator bool() { return ans; }
};
template <typename T>
ins operator>>(ins x, T &n)
{
if (!x.ans)
return x;
x.read1(n);
return x;
}
template <typename T>
ins operator<<(ins x, T n)
{
x.write1(n);
return x;
}
ins yin;
ins yout;
#endif
int main()
{
int TTT;
yin >> TTT;
while (TTT--)
{
int n, m;
yin >> n >> m;
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
char c;
yin >> c;
if (i == n)
ans += c == 'D';
if (j == m)
ans += c == 'R';
}
}
yout << ans << endl;
}
return 0;
}
|