Untitled
unknown
plain_text
2 years ago
10 kB
13
Indexable
#include<iostream>
using namespace std;
int M[25][25];
int visit[25][25];
int G[5][2];
int N,MV;
int f=-1,r=-1;
int Qx[10000];
int Qy[10000];
void push(int x,int y)
{
f++;
Qx[f] =x;
Qy[f] =y;
}
void pop(int &x, int &y)
{
r++;
x= Qx[r];
y= Qy[r];
}
int bfs(int x, int y)
{
f=r=-1;
push(x,y);
visit[x][y] =1;
while(f != r)
{
pop(x,y);
int dx[4]= { 1,-1 ,0,0};
int dy[4]= {0,0,-1,1};
for(int i=0; i<4; i++)
{
int xx= x+ dx[i];
int yy = y+dy[i];
if(xx >=1 && xx <= N && yy >=1 && yy <= N)
{
if(M[xx][yy] != 0 && visit[xx][yy] == 0)
{
push(xx,yy);
visit[xx][yy] = visit[x][y] +1;
}
}
}
}
int maxx=0;
for(int i=1; i<= MV; i++)
{
if(visit[G[i][0]][G[i][1]] > maxx) {maxx= visit[G[i][0]][G[i][1]];}
if(visit[G[i][0]][G[i][1]] == 0) return 25;
}
return maxx;
}
int main()
{
freopen("Text.txt","r",stdin);
int t;
cin >> t;
for(int stt =1; stt <=t; stt ++)
{
cin >> N >> MV;
for(int i=1; i <= MV; i++)
{
cin >> G[i][0] >> G[i][1];
}
for(int i=1; i<=N; i++)
{
for(int j=1; j<= N; j++)
{
cin >> M[i][j];
visit[i][j] =0;
}
}
for(int i=1; i <= MV; i++)
{
M[G[i][0]][G[i][1]] =2;
}
//////////////////////////////////
int minn= 25;
for(int i=1; i<=N; i++)
{
for(int j=1; j<= N; j++)
{
if(M[i][j] == 1) {
if(bfs(i,j) -1 < minn) {minn= bfs(i,j) -1 ;}
for(int q=1; q<= N; q++)
{
for(int k=1; k<=N; k++)
visit[q][k] =0;
}
}
}
}
/////////////////////////////
if(minn != 24) { cout << "Case #" << stt << endl << minn << endl;}
else { cout << "Case #" << stt << endl << "-1" << endl;}
}
return 0;
}
,,,/////////////////////////////////kim cuong
#include<iostream>
using namespace std;
int index,mark;
int Qx[10000000];
int f=-1;
int start[10000];
int cuoi[10000];
int visit[10000];
void push(int x){
f++;
Qx[f]=x;
}
void pop(int &x){
x=Qx[f];
f--;
}
void dfs(int x)
{
push(x);
while(f != -1)
{
pop(x);
for(int i=0; i<=index; i++)
{
//cout << start[i] << " " <<cuoi[i] <<" " << visit[cuoi[i]] << endl;
if(start[i] == x )
{
push(cuoi[i]);
visit[cuoi[i]] ++;
}
if(start[i] == x && visit[cuoi[i]] >= 2 )
{
mark=1;
}
}
if(mark == 1) {f=-1;}
}
}
int main()
{
//freopen("Text.txt","r",stdin);
int t;
cin >> t;
for(int stt=1; stt<=t; stt++)
{
int n;
cin >> n;
index=0;
for(int i=0; i<10000; i++)
{
start[i] =cuoi[i] =0;
}
for(int st=1; st<=n; st++)
{
int m; cin >> m;
mark =0;
for(int i=1; i<=m; i++)
{
cin >> cuoi[index];
start[index] = st;
index ++;
}
}
for(int i=1; i<=n; i++)
{
for(int j=0; j <10000; j++)
{visit[j] =0;}
dfs(i);
if(mark == 1) {break;}
}
cout << "Case #" << stt << endl;
if(mark ==1 ) { cout << "Yes" << endl;}
else {cout << "No" << endl;}
}
return 0;
}
//////////////////////////mount
#include <iostream>
#define N 305
using namespace std;
int n;
int a[N][N];
int sx[N];
int sy[N];
int dd[N][N];
int sv,sl,sc;
int minn,maxx;
int hx[]={0,-1,0,1};
int hy[]={-1,0,1,0};
void doc()
{
cin>>n;
minn=200;
maxx=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
if(a[i][j]>maxx)maxx=a[i][j];
if(a[i][j]<minn)minn=a[i][j];
}
//cout<<minn<<" ---"<<maxx<<"\n";
}
bool kt(int u,int v)
{
if(a[1][1]>v||a[1][1]<u)return false;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)dd[i][j]=0;
int dau=1,cuoi=0;
sx[++cuoi]=1;
sy[cuoi]=1;
dd[1][1]=1;
while(dau<=cuoi)
{
int x=sx[dau];
int y=sy[dau];
//cout<<x<<" "<<y<<"\n";
dau++;
for(int i=0;i<4;i++)
{
int xx=x+hx[i];
int yy=y+hy[i];
if(xx>0&&xx<=n&&yy>0&&yy<=n)
if(a[xx][yy]>=u&&a[xx][yy]<=v)
if(dd[xx][yy]==0)
{
dd[xx][yy]=1;
sx[++cuoi]=xx;
sy[cuoi]=yy;
}
}
}
//cout<<u<<" "<<v<<" "<<dd[n][n]<<"\n";
if(dd[n][n]==1)return true;
return false;
}
bool check(int k)
{
for(int i=minn;i<=maxx-k;i++)
{
//cout<<i<<" "<<i+k<<"\n";
if(kt(i,i+k))
{
//cout<<i<<"- "<<i+k<<"\n";
return true;
}
}
return false;
}
int main()
{
//freopen("input.txt","r",stdin);
int TC;
cin>>TC;
for(int tc=1;tc<=TC;tc++)
{
doc();
int lo=0,hi=maxx-minn;
while(lo<hi)
{
int mid=(lo+hi)/2;
if(check(mid))hi=mid;else lo=mid+1;
}
cout<<"#"<<tc<<" ";
cout<<lo<<"\n";
//cout<<sv<<" "<<sl<<" "<<sc<<"\n";
}
return 0;
}
//////////////////////////////nuoc bien
#include<iostream>
using namespace std;
int m,n,lev,ans;
int dem_nuoc, dem_dat;
int M[105][105];
int visit[105][105];
int f=-1, r=-1;
int Qx[100000] ;
int Qy[100000];
void push(int x, int y)
{
f++;
Qx[f] = x;
Qy[f] =y;
}
void pop(int &x,int &y)
{
r++;
x= Qx[r];
y= Qy[r];
}
void bfs_nuoc(int x,int y,int k)
{
f=r=-1;
push(x,y);
dem_nuoc++;
visit[x][y] =1;
while(f != r)
{
pop(x,y);
int dx[4]={1,-1,0,0};
int dy[4]= {0,0,1,-1};
for(int i=0; i<4; i++)
{
int xx= x +dx[i];
int yy= y +dy[i];
if(xx >=1 && xx <=m && yy >=1 && yy <=n && visit[xx][yy] == 0 && M[xx][yy] <=k)
{
push(xx,yy);
visit[xx][yy] =1;
dem_nuoc++;
}
}
}
}
void bfs_dat(int x,int y)
{
f=r=-1;
push(x,y);
dem_dat ++;
visit[x][y] =1;
while(f != r)
{
pop(x,y);
int dx[4]={1,-1,0,0};
int dy[4]= {0,0,1,-1};
for(int i=0; i<4; i++)
{
int xx= x +dx[i];
int yy= y +dy[i];
if(xx >=1 && xx <=m && yy >=1 && yy <=n && visit[xx][yy] == 0 )
{
push(xx,yy);
visit[xx][yy] =1;
dem_dat++;
}
}
}
}
void reset()
{
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
visit[i][j]=0;
}
}
int main()
{
freopen("Text.txt","r",stdin);
int stt=1;
while(1)
{
cin >> m >> n;
if(m== 0 && n== 0) {break;}
else {
int minn=1000, maxx=0;
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
{
cin >> M[i][j];
visit[i][j] =0;
if((i == 1 || i== m || j==1 || j==n) && M[i][j] < minn) { minn = M[i][j]; }
if(M[i][j] > maxx) { maxx = M[i][j];}
}
}
////////////////
ans =0;
for(lev =minn; lev <= maxx; lev++)
{
dem_dat=0 ; dem_nuoc=0;
reset();
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
{
if((i == 1 || i== m || j==1 || j==n ) && M[i][j] <= lev && visit[i][j] ==0)
{
bfs_nuoc(i,j,lev);
}
}
}
for(int i=1; i<=m; i++)
{
for(int j=1; j<=n; j++)
{
if(visit[i][j] ==0 && M[i][j] > lev)
{
bfs_dat(i,j);
i=200 ; j=200;
}
}
}
if(dem_nuoc+ dem_dat < m*n) {ans = lev; break;}
}
}
if(ans ==0 ) cout << "Case " << stt << ": Island never splits." << endl;
else cout << "Case " << stt << ": Island splits when ocean rises "<< ans << " feet." << endl;
stt++;
}
return 0;
}
////////////////////////////////well
#include<iostream>
using namespace std;
#define INF 1000000
int N;
bool Visited[100];
int key[100];
int adj[105][105];
int parent[100];
int findMin()
{
int ret = 0;
int min = INF;
for(int v =0; v < N; v++)
{
if(!Visited[v] && key[v] < min)
{
min = key[v];
ret = v;
}
}
return ret;
}
int sum_arr(int a[], int n)
{
int sum = 0;
for(int i =0; i< n; i++)
{
sum+= a[i];
}
return sum;
}
int main()
{
int T;
int res;
// freopen("Text.txt","r",stdin);
cin>>T;
for(int tc =1; tc <= T; tc++)
{
cin>>N;
for(int i = 0; i< N; i++)
{
for(int j = 0; j< N; j++)
{
cin>>adj[i][j];
}
}
for(int i =0; i< N; i++)
{
Visited[i] = false;
key[i] = INF;
parent[i] = -1;
}
key[0] = 0;
for(int i =0; i < N - 1; i++)
{
int u = findMin();
Visited[u] = true;
for(int v = 0; v < N; v++)
{
if(!Visited[v] && adj[u][v] < key[v])
{
key[v] = adj[u][v];
parent[v] = u;
}
}
}
int sum = sum_arr(key, N);
cout<<"Case #"<<tc<<endl;
cout<<sum<<endl;
}
return 0;
}
///////////////////xe tang
#include<iostream>
#define INT_MAX 2147483648
using namespace std;
char M[400][400];
long long visit[400][400];
int Qx[10000000];
int Qy[10000000];
int Qd[10000000];
int r=-1,f=-1;
void push(int x,int y ,int d){
r++;
Qx[r]=x;
Qy[r]=y;
Qd[r]=d;
}
void pop(int &x,int &y, int &d){
f++;
x=Qx[f];
y=Qy[f];
d=Qd[f];
}
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int bfs(int x,int y,int d,int ex,int ey){
push(x,y,d);
int mark =0;
while(r !=f){
pop(x,y,d);
//cheak near
for(int i=0; i<4; i++){
//is safe
int xx=x+dx[i];
int yy=y+dy[i];
if(M[xx][yy] =='E' && d+1 <visit[xx][yy] ){
push(xx,yy,d+1);
visit[xx][yy] =d+1;
}
else if(M[xx][yy] =='B' && d+2 <visit[xx][yy] ){
push(xx,yy,d+2);
visit[xx][yy] =d+2;
}
else if(M[xx][yy] =='T' && d+1 <visit[xx][yy]){
visit[xx][yy] =d+1;
mark =1;
}
}
}
if(mark ==0) return -1;
else return visit[ex][ey];
}
int main()
{
//freopen("Text1.txt","r",stdin);
int T,m,n;
int yx,yy,tx,ty;
cin >> T;
for(int tc=1; tc<= T; tc++)
{
cin >> m>>n;
//reset
for(int i=0; i<400; i++)
{
for(int j=0; j<400; j++)
{
M[i][j]= 'X';
visit[i][j]=INT_MAX;
}
}
for(int i=0; i<m; i++)
{
cin >> M[i];
//INTPUT
}
///////////////////
for(int i=0; i<m; i++)
{
for(int j=0; j<n; j++)
{
if(M[i][j]== 'Y') {yx=i; yy=j;}
else if(M[i][j] =='T') {tx=i; ty=j;}
}
}
cout << "Case #" << tc<< endl << bfs(yx,yy,0,tx,ty) << endl;
}
return 0;
}
Editor is loading...