hdu 5652
India and China Origins
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1060 Accepted Submission(s): 333
Let's assume from my crude drawing that the only way to reaching from India to China or viceversa is through that grid, blue portion is the ocean and people haven't yet invented the ship. and the yellow portion is desert and has ghosts roaming around so people can't travel that way. and the black portions are the location which have mountains and white portions are plateau which are suitable for travelling. moutains are very big to get to the top, height of these mountains is infinite. So if there is mountain between two white portions you can't travel by climbing the mountain.
And at each step people can go to 4 adjacent positions.
Our archeologists have taken sample of each mountain and estimated at which point they rise up at that place. So given the times at which each mountains rised up you have to tell at which time the communication between India and China got completely cut off.
For each test case, the first line contains two space seperated integers N,M. next N lines consists of strings composed of 0,1 characters. 1 denoting that there's already a mountain at that place, 0 denoting the plateau. on N+2 line there will be an integer Q denoting the number of mountains that rised up in the order of times. Next Qlines contain 2 space seperated integers X,Y denoting that at ith year a mountain rised up at location X,Y.
T≤10
1≤N≤500
1≤M≤500
1≤Q≤N∗M
0≤X<N
0≤Y<M
print -1 if these two countries still connected in the end.
Hint:
From the picture above, we can see that China and India have no communication since 4th year.
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int Max=;
int n,m;
int cnt;
char ch[Max];
bool used[Max][Max];
int mat[Max][Max];
int a[Max][Max];
struct node
{
int x,y;
} que[Max*Max],qq[Max*Max];
int f[Max*Max];
const int inf=Max*Max-;
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void Merge(int i,int j)
{
int t1=find(i),t2=find(j);
if(t1!=t2)
{
f[t2]=t1;
}
}
int dx[]= {,-,,};
int dy[]= {,,,-};
void solve()
{
for(int i=; i<=cnt; i++)
{
if(used[que[i].x][que[i].y]) continue;
for(int k=; k<; k++)
{
int x=que[i].x+dx[k],y=que[i].y+dy[k];
if(x<||y<||x>n||y>m) continue;
if(a[x][y]==) continue;
int j=mat[x][y];
if(used[x][y]) continue;
Merge(i,j);
}
}
}
int main()
{
int T;
for(scanf("%d",&T); T; T--)
{
scanf("%d%d",&n,&m);
cnt=;
for(int i=; i<=n; i++)
{
scanf("%s",ch);
for(int j=; j<strlen(ch); j++)
{
if(ch[j]=='')
{
a[i][j+]=;
que[++cnt].x=i;
que[cnt].y=j+;
mat[i][j+]=cnt;
}
else a[i][j+]=;
}
}
int Q,x,y;
int flag=;
memset(used,false,sizeof(used));
scanf("%d",&Q);
for(int i=; i<=Q; i++)
{
scanf("%d%d",&x,&y);
x+=;
y+=;
used[x][y]=true;
qq[i].x=x;
qq[i].y=y;
}
for(int i=; i<Max*Max; i++) f[i]=i;
for(int i=; i<=m; i++)
{
if(!used[][i])
if(a[][i]==)
Merge(inf-,mat[][i]);
if(!used[n][i])
if(a[n][i]==)
Merge(inf,mat[n][i]);
}
solve();
// cout<<find(inf-1)<<" "<<find(inf)<<endl;
int sum=Q;
while(find(inf-)!=find(inf))
{
int x=qq[Q].x,y=qq[Q].y;
used[x][y]=false;
Q--;
if(Q==-) break;
for(int k=; k<; k++)
{
int nx=x+dx[k],ny=y+dy[k];
if(nx<||ny<||nx>n||ny>m) continue;
if(used[nx][ny]) continue;
if(a[nx][ny]==)
Merge(mat[nx][ny],mat[x][y]);
}
if(x==) Merge(mat[x][y],inf-);
if(x==n) Merge(mat[x][y],inf);
}
printf("%d\n",Q==sum?-:Q+);
}
return ;
}
最新文章
- 安装 mysql-5.7.5-m15-winx64
- 7.添加基于Spring的WebService拦截器
- volley post非json格式数据并获取json数据
- ubuntu安装hadoop2.6
- HDU 4565 So Easy!(矩阵)
- 函数page_rec_get_next_const
- Linux 经典面试题
- JavaScript之面向对象学习三原型语法升级
- WPF ListBox 一些小知识点
- Linux 安装 MongoDB
- Java学习NO.2
- CSS3中设置字体的抗锯齿或光滑度的属性
- 2、Linux安装jmeter
- es6 语法 (let 和const)
- npm --save-dev 和--save 参数的区别
- 《Linux内核设计与实现》读书笔记三
- Bootstrap手风琴效果
- Redis源码学习-Master&;Slave的命令交互
- appium 获取android 粘贴板上的内容
- 识别图片验证码的三种方式(scrapy模拟登陆豆瓣网)
热门文章
- Mongo性能测试-python脚本
- java 多线程——同步 学习笔记
- C#的内存管理知识 .
- 神经网络结构设计指导原则——输入层:神经元个数=feature维度 输出层:神经元个数=分类类别数,默认只用一个隐层 如果用多个隐层,则每个隐层的神经元数目都一样
- B1297 [SCOI2009]迷路 矩阵
- Hyper-v 3.0 安装centos6.3
- istio-禁用/允许sidecar设置
- Linux基本命令 文件管理 下部
- Unity项目 - 吃豆人Pacman
- Unity3d dotween