这个题的关键在于那些？的要求，因为是？所以不用一下子满足，这就是这个题的玄机了。
于是我们可以“顺便”把这些 “对于当前关是？，但是对于以后的关不是？” 的灯给进行操作。
这样就可以减少次数了。
#include<iostream> #include<string.h> #include<string> #include<algorithm> #include<stdio.h> #define LL long long int using namespace std; char mp[60][60]; char now[60]; int n,m; int work() { int cnt = 0; for(int i = 0;i<m;i++) now[i] = '-'; for(int rd = 0;rd < n;rd++) { //看看有没有必须变成+的 bool hsp = false;//have to become plus; for(int j = 0;j<m;j++) { if(mp[rd][j] == '+' && now[j] == '-') { hsp = true; now[j] = '+'; } } if(hsp == true)//看看可不可以顺便变掉 { cnt ++; for(int j = 0;j<m;j++) { for(int k = rd;k<n;k++) { if(mp[k][j] == '-') break; if(mp[k][j] == '+') { now[j] = '+'; break; } } } } bool hsm = false; for(int j = 0;j<m;j++) { if(mp[rd][j] == '-' && now[j] == '+') { hsm = true; now[j] = '-'; } } if(hsm == true)//看看可不可以顺便变掉 { cnt ++; for(int j = 0;j<m;j++) { for(int k = rd;k<n;k++) { if(mp[k][j] == '+') break; if(mp[k][j] == '-') { now[j] = '-'; break; } } } } cnt ++; } return cnt; } int main() { int TT; cin>>TT; while(TT--) { //init(); cin>>n>>m; for(int i = 0;i<n;i++) scanf("%s",mp[i]); int ans = work(); cout<<ans<<endl; } return 0; }
