/* 这题之前一度会错意了,没理解“只允许交换相邻的两行”,意味着只能整行交换 以及,最后要保证,每行最后出现1的位置,不得大于该行的行数 又及,这题一开始...没看输入数据,以为输入数据之间是有空格的,相当于一个一个数字输入,后来看完数据格式才发现,其实应该输入一串字符串,然后分离为一个个数字 */
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAX_N = 45; int N; int M[MAX_N][MAX_N]; // 矩阵 int a[MAX_N]; // a[i]表示第i行最后出现1的位置: 1~n-1 void solve() { fill (a, a + N, -1); int res = 0; // cout << "call solve and res = " << res << endl; for (int i = 0; i < N; i++) { a[i] = -1; // 如果第i行不含1的话,就当作-1 for (int j = 0; j < N; j++) if (M[i][j] == 1) a[i] = j; } for (int i = 0; i < N; i++) { int pos = -1; // 要移动到第i行的行 for (int j = i; j < N; j++) { if (a[j] <= i) { pos = j; break; } } for (int j = pos; j > i; j--) { // cout << "nwo j = " << j << " and pos = " << pos << endl; swap(a[j], a[j - 1]); res++; // cout << "now res = " << res << endl; } } cout << res << endl; } int main() { freopen("E:\A-large.txt", "r", stdin); freopen("E:\output2.txt", "w", stdout); int k; cin >> k; for (int kase = 1; kase <= k; kase++ ) { cin >> N; for (int i = 0; i < N; i++) { char s[MAX_N]; cin >> s; for (int j = 0; j < N; j++) M[i][j] = s[j] - '0'; } // for (int i = 0; i < N; i++) // for (int j = 0; j < N; j++) // cin >> M[i][j]; printf("Case #%d: ",kase); solve(); } fclose(stdin); fclose(stdout); return 0; }