首页 > 代码库 > 2014 Super Training #4 D Paint the Grid Again --模拟

2014 Super Training #4 D Paint the Grid Again --模拟

2024-07-10 13:29:38   222人阅读

原题：ZOJ 3780 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3780

刚开始看到还以为是搜索题，没思路就跳过了。结果后来发现就是一个简单的模拟啊，因为每行每列都只能消去一次，直接慢慢消去就好了，因为按字典序从小到大，那就按行从大到小，列从大到小的顺序来消就可以了，消完了标记一下，把那行或者那列的元素都赋为一个特殊的字符‘*‘即可。

还是应该多思考啊，不要被题目吓到了。探寻题目的本质才能更好的解题。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <map>using namespace std;#define N 14pair<char,int> ans[250020];char ss[506][506];int Rvis[506],Cvis[506];int main(){    int t,n,i,j;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        for(i=0;i<n;i++)            scanf("%s",ss[i]);        memset(Rvis,0,sizeof(Rvis));        memset(Cvis,0,sizeof(Cvis));        int flag = 0;        int o,x,h;        int k = 0;        while(!flag)        {            flag = 1;            //行X            for(i=n-1;i>=0;i--)            {                if(Rvis[i])                    continue;                o = x = h = 0;                for(j=0;j<n;j++)                {                    if(ss[i][j] == ‘X‘)                        x++;                    else if(ss[i][j] == ‘O‘)                        break;                    else                        h++;                }                if(j == n && h != n)  //没有出现O且不全为‘*‘                {                    Rvis[i] = 1;                    ans[k].first = ‘R‘;                    ans[k++].second = i+1;                    for(j=0;j<n;j++)                        ss[i][j] = ‘*‘;                    flag = 0;                    break;                }                else if(h == n)                    Rvis[i] = 1;            }            if(!flag)                continue;            //列O            for(j=n-1;j>=0;j--)            {                if(Cvis[j])                    continue;                o = x = h = 0;                for(i=0;i<n;i++)                {                    if(ss[i][j] == ‘X‘)                        break;                    else if(ss[i][j] == ‘O‘)                        o++;                    else                        h++;                }                if(i == n && h != n) //没有出现X且不全为‘*‘                {                    Cvis[j] = 1;                    ans[k].first = ‘C‘;                    ans[k++].second = j+1;                    for(i=0;i<n;i++)                        ss[i][j] = ‘*‘;                    flag = 0;                    break;                }                else if(h == n)                    Cvis[j] = 1;            }        }        int tag = 1;        for(i=0;i<n;i++)            for(j=0;j<n;j++)                if(ss[i][j] != ‘*‘)                {                    tag = 0;                    break;                }        if(!tag)            puts("No solution");        else        {            printf("%c%d",ans[k-1].first,ans[k-1].second);            for(i=k-2;i>=0;i--)                printf(" %c%d",ans[i].first,ans[i].second);            printf("\n");        }    }    return 0;}
View Code

 


联系
我们