ZOJ - 3780 Paint the Grid Again （拓扑排序）

Myth丶恋晨 2022-05-26 05:28 10阅读 0赞

这题主要把握两点：1.  完整的一行一定是在最后涂的

2.顺最小字典序就是逆最大字典序。

#include<cstdio>
    #include<cmath>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const double ep=1e-10;
    const int INF=0x3f3f3f3f;
    int n, nc, nr;
    char mp[510][510];
    int R[510], C[510];
    stack<int> ans;
    priority_queue< int, vector<int>, less<int> > qr, qc;
    
    void init(){
    	while(!ans.empty()) ans.pop();
    	while(!qr.empty()) qr.pop();
    	while(!qc.empty()) qc.pop();
    	memset(R, 0, sizeof(R));
    	memset(C, 0, sizeof(C));
    	nc=nr=0;
    }
    
    void erasec(int c){
    	nc++;
    	for(int i=0; i<n; i++)
    	{
    		if(R[i]!=0){
    			 R[i]++; if(R[i]==n) qr.push(i);	
    		}
    	}
    	
    }
    
    void eraser(int r){
    	nr++;
    	for(int i=0; i<n; i++)
    	{
    		if(C[i]!=0){
    			C[i]++; if(C[i]==n) qc.push(i);	
    		}
    	}
    }
    
    void solve(){
    	
    	while(!qr.empty() || !qc.empty() ){
    		
    		
    		while(!qr.empty())
    		{
    			eraser(qr.top());
    			ans.push(qr.top() + 2000+1);
    			R[qr.top()]=0;
    			qr.pop();
    		}
    		
    		while(!qc.empty())
    		{
    			erasec(qc.top());
    			ans.push(qc.top() + 1000+1);
    			C[qc.top()]=0;
    			qc.pop();
    		}
    		
    	}
    	
    }
    
    void showans(){
    	while(!ans.empty()){
    		printf("%c%d", ans.top()/1000==1?'C':'R', ans.top()%1000);
    		ans.pop();
    		if(ans.size()==0)
    			puts("");
    		else
    			printf(" ");
    	}
    }
    
    int main() {
    	int T;
    	scanf("%d", &T);
    	while(T--) {
    		init();
    		scanf("%d", &n);
    		for(int i=0; i<n; i++)
    			scanf("%s", mp[i]);
    		
    		for(int i=0; i<n; i++)
    		{
    			for(int j=0; j<n; j++)
    				if(mp[i][j]=='X')
    				{
    					R[i]++; if(R[i]==n) qr.push(i); 
    				}
    				else{
    					C[j]++; if(C[j]==n) qc.push(j);
    				}
    		}
    		solve();
    		if(nc!=n && nr!=n)
    			printf("No solution\n");
    		else
    			showans();
    	}
    
    	return 0;
    }