pojWindow Pains(拓扑排序)
题目链接:
题意:
一快屏幕分非常多区域,区域之间能够相互覆盖,要覆盖就把属于自己的地方所有覆盖。
给出这块屏幕终于的位置。看这块屏幕是对的还是错的。。
思路:
拓扑排序,这个简化点说,就是说跟楚河汉界一样。。分的清清楚楚,要么这块地方是我的,要么这块地方是你的,不纯在一人一办的情况,所以假设排序的时候出现了环,那么就说这快屏幕是坏的。。
。另一点细节要注意的是第i个数字究竟属于第几行第几列。所以这个要发现规律,然后一一枚举就能够了。。
题目:
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 1588 | Accepted: 792 |
Description
and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux's windows would be represented by the following 2 x 2 windows:
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window 1and then window 2 were brought to the foreground, the resulting representation
would be:
|
If window 4 were then brought to the foreground: |
|
. . . and so on . . .
Unfortunately, Boudreaux's computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly.
And this is where you come in . . .
Input
A single data set has 3 components:
- Start line - A single line:
START - Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux's screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers
on each line will be delimited by a single space. - End line - A single line:
END
After the last data set, there will be a single line:
ENDOFINPUT
Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.
Output
THESE WINDOWS ARE CLEAN
Otherwise, the output will be a single line with the statement:
THESE WINDOWS ARE BROKEN
Sample Input
START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT
Sample Output
THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN
Source
代码为:
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=5+10;
int map[maxn][maxn],in[maxn];
queue<int>Q;
vector<int>vec[maxn];
int dx[]={0,0,1,1};
int dy[]={0,1,0,1};
int topo()
{
int sum=9;
while(!Q.empty()) Q.pop();
for(int i=1;i<=9;i++)
{
if(in[i]==0)
Q.push(i);
}
while(!Q.empty())
{
int temp=Q.front();
Q.pop();
sum--;
for(int i=0;i<vec[temp].size();i++)
{
if(--in[vec[temp][i]]==0)
Q.push(vec[temp][i]);
}
}
if(sum>0) return 0;
else return 1;
}
void init()
{
char str[10];
for(int i=1;i<=9;i++)
{
vec[i].clear();
in[i]=0;
}
for(int i=1;i<=9;i++)
{
int x=(i-1)/3+1;
int y=i%3==0?
3:i%3;
for(int j=0;j<=3;j++)
{
int tx=x+dx[j];
int ty=y+dy[j];
if(map[tx][ty]!=i)
{
vec[i].push_back(map[tx][ty]);
in[map[tx][ty]]++;
}
}
}
scanf("%s",str);
}
void solve()
{
int ans=topo();
if(ans)
cout<<"THESE WINDOWS ARE CLEAN"<<endl;
else
cout<<"THESE WINDOWS ARE BROKEN"<<endl;
}
int main()
{
char str[10];
while(~scanf("%s",str))
{
if(strcmp(str,"ENDOFINPUT")==0) return 0;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
scanf("%d",&map[i][j]);
init();
solve();
}
return 0;
}
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=5+10;
int map[maxn][maxn],in[maxn]; queue<int>Q;
vector<int>vec[maxn];
int dx[]={0,0,1,1};
int dy[]={0,1,0,1}; int topo()
{
int sum=9;
while(!Q.empty()) Q.pop();
for(int i=1;i<=9;i++)
{
if(in[i]==0)
Q.push(i);
}
while(!Q.empty())
{
int temp=Q.front();
Q.pop();
sum--;
for(int i=0;i<vec[temp].size();i++)
{
if(--in[vec[temp][i]]==0)
Q.push(vec[temp][i]);
}
}
if(sum>0) return 0;
else return 1;
} void init()
{
char str[10];
for(int i=1;i<=9;i++)
{
vec[i].clear();
in[i]=0;
}
for(int i=1;i<=9;i++)
{
int x=(i-1)/3+1;
int y=i%3==0? 3:i%3;
for(int j=0;j<=3;j++)
{
int tx=x+dx[j];
int ty=y+dy[j];
if(map[tx][ty]!=i)
{
vec[i].push_back(map[tx][ty]);
in[map[tx][ty]]++;
}
}
}
scanf("%s",str);
} void solve()
{
int ans=topo();
if(ans)
cout<<"THESE WINDOWS ARE CLEAN"<<endl;
else
cout<<"THESE WINDOWS ARE BROKEN"<<endl;
} int main()
{
char str[10];
while(~scanf("%s",str))
{
if(strcmp(str,"ENDOFINPUT")==0) return 0;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
scanf("%d",&map[i][j]);
init();
solve();
}
return 0;
}
最新文章
- 老男孩python自动化运维作业1
- [SLAM]2D激光线特征提取
- 解决Mac下GDB提示签名错误
- Difference Search Path
- Sbt的使用初步和用sbt插件生成eclipse工程
- urlrewrite 地址重写
- c#中的枚举
- editplus的配置文件来支持sql语法高亮【转】
- Android中文乱码彻底解决
- [Effective C++ --017]以独立语句将newed对象置入智能指针
- NIO学习:buffer读入与写出(文件复制示例)
- angularjs使用directive实现倒计时按钮
- android.telephony.SmsManager 短信笔记
- [转载] ZooKeeper原理及使用
- C# — 实现软件开机自启功能(不需要管理员权限)
- angular 的navigate 各种使用情况
- 一个跳转提示页面---JS
- hdu 1509 &; hdu 1873 &; hdu 1896 (基础优先队列)
- vuex 的使用
- POJ--2406Power Strings+KMP求字符串最小周期