C. Removing Columns
time limit per test
memory limit per test
input
output
n × m
abcd edfg hijk
we obtain the table:
acd efg hjk
good
Input
n and m (1 ≤ n, m ≤ 100).
n lines contain m
Output
Print a single number — the minimum number of columns that you need to remove in order to make the table good.
Examples
input
1 10 codeforces
output
0
input
4 4 case care test code
output
2
input
5 4 code forc esco defo rces
output
4
Note
In the first sample the table is already good.
In the second sample you may remove the first and third column.
In the third sample you have to remove all the columns (note that the table where all rows are empty is considered good by definition).
s and t have equal length. Then, s is lexicographically larger than t if they are not equal and the character following the largest common prefix of s and t (the prefix may be empty) in s is alphabetically larger than the corresponding character of t.
#include <bits/stdc++.h>
#define INF 1e18
#define maxn 105
using namespace std;
typedef long long ll;
struct Node{
Node(int a, int b){
l = a;
r = b;
}
int l, r;
};
char str[maxn][maxn];
deque<Node> q;
bool judge(int c){
for(int i = 0; i < q.size(); i++){
for(int j = q[i].l+1; j <= q[i].r; j++){
if(str[j][c] < str[j-1][c])
return false;
}
}
return true;
}
int main(){
// freopen("in.txt", "r", stdin);
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%s", str[i]+1);
q.push_back(Node(1, n));
int ans = 0, c = 1;
while(!q.empty() && c <= m){
if(judge(c) == false){
ans++;
c++;
continue;
}
int k = q.size();
while(k--){
int i = q[0].l + 1, r;
while(i <= q[0].r){
int l = i-1;
while(str[i][c] == str[i-1][c] && i <= q[0].r)
i++;
r = i-1;
i++;
if(r > l)
q.push_back(Node(l, r));
}
q.pop_front();
}
c++;
}
cout << ans << endl;
return 0;
}