Mendo Judge Discussion Board - Forums
Search
Recent Topics
Hottest Topics
Member Listing
Back to home page
Messages posted by: KRISS
Forum Index
»
Profile for KRISS
»
Messages posted by KRISS
Author
Message
Задачи од национални натпревари
»
Задача Скокови
»
Go to message
#include <iostream> #include <stack> #include <algorithm> #include <cstring> #include <vector> using namespace std; int N,M; bool WithinRange(int x, int y) { if((x>=0 && x<N) && (y>=0 && y<M)) return true; return false; } int main() { cin>>N>>M; int MAT[N][M]; vector<pair<int, int> > cords; for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { cin>>MAT[i][j]; if(MAT[i][j]==1) cords.push_back(make_pair(i,j)); } } stack<pair<int, int> > s; bool VIS[N][M]; memset(VIS,false,sizeof(VIS)); bool VIS1[N][M]; memset(VIS1,false,sizeof(VIS)); int delta_x[]={0,0,1,-1}; int delta_y[]={1,-1,0,0}; for(int i=0;i<cords.size();i++) { pair<int, int> at1=cords[i]; memset(VIS,false,sizeof(VIS)); int potek=0; if(VIS1[at1.first][at1.second]==false) { VIS1[at1.first][at1.second]=true; s.push(at1); while(!s.empty()) { pair<int,int> at=s.top(); s.pop(); if(potek%2!=0) { for(int dir=0;dir<2;dir++) { int x=at.first, y=at.second; int next_x=x+delta_x[dir], next_y=y+delta_y[dir]; if(WithinRange(next_x,next_y)==true && VIS[next_x][next_y]==false && MAT[next_x][next_y]!=0) { s.push(make_pair(next_x, next_y)); VIS[next_x][next_y]=true; potek++; if(potek==cords.size()) { cout<<"DA"<<endl; return 0; } } } } if(potek%2==0) { for(int dir=2;dir<4;dir++) { int x=at.first, y=at.second; int next_x=x+delta_x[dir], next_y=y+delta_y[dir]; if(WithinRange(next_x, next_y)==true && VIS[next_x][next_y]==false && MAT[next_x][next_y]!=0) { s.push(make_pair(next_x, next_y)); VIS[next_x][next_y]=true; potek++; if(potek==cords.size()) { cout<<"DA"<<endl; return 0; } } } } } } } cout<<"NE"<<endl; return 0; }
Ја решавав оваа задача со ДФС. но ми работи само на 32/50 малку помош!!!
Forum Index
»
Profile for KRISS
»
Messages posted by KRISS
Go to:
Select a forum
Добродојдовте!
Општа дискусија
Задачи од национални натпревари
Задачи од меѓународни натпревари
Други задачи
Регионални натпревари
Државни натпревари
Македонски Олимпијади
Други натпревари
Pascal
C/C++
Јава
Други јазици
Powered by
JForum 2.1.8
©
JForum Team