本文主要是介绍zoj3780 Paint the Grid Again 拓扑排序模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
比赛时候看完题目就觉得是拓扑排序，当时心里隐隐觉得跟相框叠加那个题有点相似的
然后wzy问我no solution 是什么情况，我就一直去想是不是构成了什么排列就一定是no solution
其实只用再参考相框叠加那个题往前想一丁点就够了，就是从最后涂的那一层开始往前找，每一次都必然有一行或一整列是一样的
每次按逆字母序删除这一行或列就是了。
拓扑排序的题总是类似而且简单的，找到关系，敲代码完全不存在问题。
题意：
给一块n*n的格子，每次可以将任意行变成X，或任意列变成O，后操作的将覆盖原先的操作。给出最终图形，要求按先后顺序输出操作方法。
思路：
对于任一时刻，最后操作的一行或一列颜色（指X或O）肯定相同。
那么我们从最终的图案倒着往前模拟，按逆字母序（题目要求字母序，我们要倒着来）查找是否存在一行或一列完全相同，找到之后直接删除（因为这一行或列下面覆盖的可以是任意的，想要X就是X，想要O就是O），这样如果可以把整个图都删完，就说明有解，按顺序输出即可。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
using namespace std;struct node
{char dir;int index;
}ans[1010];int r[510],c[510],n;
char mp[510][510];bool ok()
{for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(mp[i][j]!='.')return 1;return 0;
}int main()
{int t,i,j,flag,cnt;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++)scanf("%s",mp[i]);memset(c,0,sizeof c);memset(r,0,sizeof r);cnt=0;flag=1;while(ok()){/* for(i=0;i<n;i++,putchar('\n'))for(j=0;j<n;j++)putchar(mp[i][j]);*///从最后一次操作开始找 要使顺序是字母序 那么倒着找就是逆字母序//因此 先R后C 从右下到左上if(flag==0) break;//没找到符合的行列 且整个没有结束for(i=n-1;i>=0;i--){if(r[i]) continue;flag=1;for(j=0;j<n;j++){if(c[j]) continue;if(mp[i][j]!='X'){flag=0;break;}}if(flag){for(j=0;j<n;j++)mp[i][j]='.';r[i]=1;ans[cnt].dir='R';ans[cnt].index=i+1;cnt++;break;}}if(flag) continue;for(i=n-1;i>=0;i--){if(c[i]) continue;flag=1;for(j=0;j<n;j++){if(r[j]) continue;if(mp[j][i]!='O'){flag=0;break;}}if(flag){for(j=0;j<n;j++)mp[j][i]='.';c[i]=1;ans[cnt].dir='C';ans[cnt].index=i+1;cnt++;break;}}}if(flag){for(i=cnt-1;i>0;i--)printf("%c%d ",ans[i].dir,ans[i].index);printf("%c%d\n",ans[i].dir,ans[i].index);}else printf("No solution\n");}return 0;
}
这篇关于zoj3780 Paint the Grid Again 拓扑排序模拟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
