#include <iostream> #include <cstdio> #include <vector> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <fstream> #include <string> #include <algorithm> #define INF 1000000000 #define ll long long using namespace std; int h,w; string arr[1010]; bool visit[1010][1010]; int stateCount[26]; struct stateInfo{ int count; int name; }; vector<stateInfo> vb; bool cmp(stateInfo a,stateInfo b) { if(a.count!=b.count) return a.count>b.count;
Category: DFS AND BFS
521
#include <iostream> #include <cstdio> #include <vector> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> using namespace std; int n,d,s; int BusStartAtStop[51]; int BusRunAtRoad[51]; int gr[31][31]; bool visit[51][51]; vector<int> vRoadstops[21]; vector<int> vBusRunAtRoad[21]; void init() { for(int i=0;i<51;i++) { BusStartAtStop[i]=0; BusRunAtRoad[i]=0; } for(int i=0;i<31;i++) for(int j=0;j<31;j++) gr[i][j]=0; for(int i=0;i<21;i++) { vRoadstops[i].clear(); vBusRunAtRoad[i].clear(); } } void
794
This one took me a looong time to figure out the solution, i used dynamic programming approach to modify the bfs traversal. #include <iostream> #include <cstdio> #include <cstdlib> #include <vector> #include <cstring> #include <fstream> #include <string> #include <map> #include <queue> #define INF 100000000 //#define ll long long #define PASS 2 #define NEED 1 #define NONEED
710
This is quite an easy problem. But it took me long time to realize that to determine the number of total game segments is nothing but counting the direction changes to reach the destination. #include <iostream> #include <cstdio> #include <climits> #include <queue> #include <cstring> #include <string> using namespace std; int w,h; int SEGMENT; int gr[80][80];
633
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std; int stx,sty,edx,edy; int gr[405][405]; int dirx[8]={-2,-2,2,2,1,1,-1,-1}; int diry[8]={1,-1,1,-1,2,-2,2,-2}; int dx[4]={2,2,-2,-2}; int dy[4]={-2,2,2,-2}; int n; int bfs() { queue<int> q; int x,y; //int visit[405][405]; //memset(visit,0,sizeof(visit)); int moveTyp=0,move; int step=0,stepCount; q.push(stx);q.push(sty);q.push(moveTyp);q.push(step); if(gr[stx][sty]==1) return -1; else if(gr[edx][edy]==1) return -1; while(!q.empty()) { x = q.front();q.pop(); y
627
#include <iostream> #include <cstdio> #include <sstream> #include <vector> #include <string> #include <cstring> #include <queue> using namespace std; vector<int> vb[305]; vector<int> par; bool bfs(int path[],int st,int ed) { int visit[400]; for(int i=0;i<400;i++) visit[i]=0; queue<int> q; q.push(st); visit[st]=1; int a,b; if(st==ed) return 1; while(!q.empty()) { a = q.front();q.pop(); if(a==ed) return 1; for(int i=0;i<vb[a].size();i++) { b = vb[a][i];
321
I used bit operation to represent the states of the switches state of the villa. #include <iostream> #include <cstdio> #include <vector> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> using namespace std; struct Point{ int x,y; }; int kase=1; Point points[11500]; int arr[11][1024]; int array_map_par[11500]; bool door[15][15]; bool light_swtch[15][15]; bool flag; int RR,DD,SS;
314
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <string> #define NORTH 0 #define EAST 1 #define SOUTH 2 #define WEST 3 using namespace std; struct State{ int x,y,dir; int val; }; int r,c; int gr[55][55][4]; string face; int bx,by,ex,ey; void bfs() { int dir; queue<int> q; if(face=="south") dir=SOUTH; else if(face=="north") dir=NORTH; else if(face=="east") dir=EAST;
298
#include <iostream> #include <cstdio> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> using namespace std; bool gr[30][30][7][7]; //bool gr2D[30][30]; struct Point{ int x,y,velocity,accleration; int val; }; Point St,Fn; int m,n; void bfs() { int x,y,v,a,val; int dx,dy,tx,ty; queue<int> q; q.push(St.x);q.push(St.y); q.push(0);q.push(0);q.push(0); gr[St.x][St.y][0+3][0+3]=1; while(!q.empty()) { x=q.front();q.pop(); y=q.front();q.pop(); v=q.front();q.pop(); a=q.front();q.pop(); val = q.front();q.pop(); //cout<<x<<" "<<y<<"
10067
#include <iostream> #include <queue> using namespace std; bool visit[10][10][10][10]; int arr[3]={0,1,-1}; struct states{ int a,b,c,d; int step; }; int main() { int t,n,stp; states tmp; int tw,tx,ty,tz; int a,b,c,d,x,y,w,z; cin>>t; while(t–) { states src,trgt,tmp; for(int i=0;i<10;i++) for(int j=0;j<10;j++) for(int k=0;k<10;k++) for(int l=0;l<10;l++) visit[i][j][k][l]=0; cin>>a>>b>>c>>d; src.a=a; src.b=b; src.c=c; src.d=d; src.step=0; cin>>a>>b>>c>>d; trgt.a=a; trgt.b=b; trgt.c=c; trgt.d=d; trgt.step=-1;