SP7555题解
Nahia
·
·
题解
思路
那直接 bfs $^\texttt{1}$ 吧。
但是还要加点**贪心**的思路，遍历所有行，如果这一行不合法，就和下面第一个合法的行交换，如果这一行合法就直接跳过。
### solution
```cpp
#include<bits/stdc++.h>
#define For(i,a,b) for(int i = a;i<=b;i++)
using namespace std;
inline __int128 read(){__int128 x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
inline void write(__int128 x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
int n,a[1005],t,sum;
char b;
int main(){
t = read();
For(l,1,t){
n = read();
memset(a,0,sizeof(a));//多测清空好习惯
sum = 0;
For(i,1,n){
For(j,1,n){
cin>>b;
if(b=='1') a[i] = j;
}
}
For(i,1,n){
if(a[i]<=i) continue;
For(j,i+1,n){
if(a[j]<=i){
sum+= j-i;
for(j = j;j>i;j--) a[j]=a[j-1];
break;
}
}
}
printf("Case #%d: %d\n",l,sum);
}
}
```
### 注意
看到是 SPOJ 的题目，意识到注意**输出格式**。