API tools faq
paste
Josif_tepe

Untitled

Josif_tepe
Apr 16th, 2022
175
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.17 KB | None | 0 0
raw download clone embed print report
  1. #include <vector>
  2. #include <sstream>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cstring>
  6. #include <string>
  7. #include <cstdlib>
  8. #include <cstdio>
  9. #include <map>
  10. #include <list>
  11. #include <queue>
  12. #include <set>
  13.  
  14. using namespace std;
  15.  
  16. class ChessMaze
  17. {
  18.   public:
  19.  
  20.     int traverseMaze( vector<string> maze )
  21.     {
  22.     int n=maze.size();
  23.     int m=maze[0].size();
  24.         cout << n << " " << m << endl;
  25.     int mat[n][m];
  26.  
  27.     int si=0;
  28.     int sj=0;
  29.  
  30.     int ei=0;
  31.     int ej=0;
  32.  
  33.     int c=0;
  34.  
  35.     bool visited[n][m][1 << 11][15];
  36.     for(int i=0; i<n; i++){
  37.         for(int j=0; j<m; j++){
  38.             if(maze[i][j]=='K'){
  39.  
  40.             mat[i][j]=c;
  41.  
  42.             c++;
  43.             }
  44.             if(maze[i][j]=='S'){
  45.              si=i;
  46.              sj=j;
  47.             }
  48.              if(maze[i][j]=='E'){
  49.                 ei=i;
  50.                 ej=j;
  51.              }
  52.            
  53.         }
  54.     }
  55.  
  56.     int di[]={0, 0, 1, -1};
  57.     int dj[]={1, -1, 0, 0};
  58.  
  59.         int ki[] = {-2, -2,  -1, -1, 1, 1, 2, 2};
  60.                 int kj[] = {1, -1,    2, -2, -2, 2, -1, 1};
  61.          
  62.  
  63.     memset(visited, false, sizeof visited);
  64.  
  65.  
  66.         maze[ei][ej] = '.';
  67.    queue<int>q;
  68.    q.push(si);
  69.    q.push(sj);
  70.    q.push(0);/// powerups
  71.    q.push(0);
  72.    q.push(0);
  73.         visited[si][sj][0][0] = true;
  74.    while(!q.empty()){
  75.     int ci=q.front();
  76.     q.pop();
  77.     int cj=q.front();
  78.     q.pop();
  79.     int bitmask=q.front();
  80.     q.pop();
  81.     int mozni=q.front();
  82.     q.pop();
  83.     int cekori=q.front();
  84.     q.pop();
  85.  
  86.     if(ci == ei and cj == ej){
  87.         return cekori;
  88.     }
  89.     for(int i=0; i<4; i++){
  90.     int ti=ci+di[i];
  91.     int tj=cj+dj[i];
  92.     if((ti>=0)and(ti<n)and(tj>=0)and(tj<m)and(maze[ti][tj]!='*')){
  93.        if(((maze[ti][tj]=='.')or(maze[ti][tj]=='E'))and(visited[ti][tj][bitmask][mozni]==false)){
  94.         q.push(ti);
  95.         q.push(tj);
  96.         q.push(bitmask);
  97.         q.push(mozni);
  98.         q.push(cekori+1);
  99.         visited[ti][tj][bitmask][mozni]=true;
  100.        }
  101.        if(maze[ti][tj]=='K'){
  102.         int def=(mat[ti][tj]);
  103.         int novamaska=(bitmask | (1 << def));
  104.  
  105.         int x=0;
  106.  
  107.         if((bitmask & (1 << def)) == 0){
  108.             x = 1;
  109.         }
  110.            
  111.         if(visited[ti][tj][novamaska][mozni+x]==false){
  112.         q.push(ti);
  113.         q.push(tj);
  114.         q.push(novamaska);
  115.         q.push(mozni+x);
  116.         q.push(cekori+1);
  117.             visited[ti][tj][novamaska][mozni + x] = true;
  118.         }
  119.        }
  120.     }
  121.     }
  122.  
  123.     if(mozni>0){
  124.             for(int i=0; i<8; i++){
  125.             int ti=ci+ki[i];
  126.             int tj=cj+kj[i];
  127.             if((ti>=0)and(ti<n)and(tj>=0)and(tj<m)and(maze[ti][tj]!='*')){
  128.        if(((maze[ti][tj]=='.')or(maze[ti][tj]=='E'))and(visited[ti][tj][bitmask][mozni-1]==false)){
  129.         q.push(ti);
  130.         q.push(tj);
  131.         q.push(bitmask);
  132.         q.push(mozni-1);
  133.         q.push(cekori+1);
  134.         visited[ti][tj][bitmask][mozni - 1]=true;
  135.        }
  136.        if(maze[ti][tj]=='K'){
  137.         int def=(mat[ti][tj]);
  138.         int novamaska=(bitmask | (1 << def));
  139.  
  140.         int x=0;
  141.            
  142.            if((bitmask & (1 << def)) == 0){
  143.                x = 1;
  144.            }
  145.            
  146.         if(visited[ti][tj][novamaska][mozni+x-1]==false){
  147.         q.push(ti);
  148.         q.push(tj);
  149.         q.push(novamaska);
  150.         q.push(mozni+x-1);
  151.         q.push(cekori+1);
  152.             visited[ti][tj][novamaska][mozni + x - 1] = true;
  153.         }
  154.        }
  155.  
  156.        }
  157.  
  158.     }
  159.     }
  160.    
  161.     }
  162.     return -1;
  163.  
  164.  
  165.  
  166.  
  167.  
  168. }
  169. };
  170. /*
  171.  {"*........**K*.",".****....****.","*.***.**S.K*..","***..***.*....","E..*...***...*","**...**..*..*K",".*..*.*...*...","..*.*.*.......","......*.*.....",".*..***.***..*",".**.**.***.**.","*.*......**.*.","**.*....*...**"}
  172.  */
  173. const int Test_No=0;
  174.  
  175. int main()
  176. {
  177.   ChessMaze tmp;
  178.   int res;
  179.   vector<string> *maze;
  180. /***************************Test 1 ********************************/
  181.  
  182. if(Test_No==0 || Test_No==1){
  183.     string ABC0[]= {"*........**K*.",".****....****.","*.***.**S.K*..","***..***.*....","E..*...***...*","**...**..*..*K",".*..*.*...*...","..*.*.*.......","......*.*.....",".*..***.***..*",".**.**.***.**.","*.*......**.*.","**.*....*...**"};
  184.  
  185. maze= new vector<string> (&ABC0[0],&ABC0[13]);
  186. res = tmp.traverseMaze(*maze);
  187. if(res == 14) cout<<"test #"<<1<<" Correct!\n\n";
  188.   else {cout<<"test #"<<1<<" Wrong!\n";
  189. cout<<"Expected: "<<14<<"\n";
  190. cout<<"Recieved: "<< res <<" \n\n";}
  191. cout<<"---------------------------------------------"<<"\n";
  192.  
  193. }
  194. /******************************************************************/
  195.  
  196.  
  197. /***************************Test 2 ********************************/
  198.  
  199. if(Test_No==0 || Test_No==2){
  200. string ABC1[]={".SE","KKK"};
  201. maze= new vector<string> (&ABC1[0],&ABC1[2]);
  202. res = tmp.traverseMaze(*maze);
  203. if(res == 1) cout<<"test #"<<2<<" Correct!\n\n";
  204.   else {cout<<"test #"<<2<<" Wrong!\n";
  205. cout<<"Expected: "<<1<<"\n";
  206. cout<<"Recieved: "<< res <<" \n\n";}
  207. cout<<"---------------------------------------------"<<"\n";
  208.  
  209. }
  210. /******************************************************************/
  211.  
  212.  
  213. /***************************Test 3 ********************************/
  214.  
  215. if(Test_No==0 || Test_No==3){
  216. string ABC2[]={"K.",".S","..",".*","*E"};
  217. maze= new vector<string> (&ABC2[0],&ABC2[5]);
  218. res = tmp.traverseMaze(*maze);
  219. if(res == 5) cout<<"test #"<<3<<" Correct!\n\n";
  220.   else {cout<<"test #"<<3<<" Wrong!\n";
  221. cout<<"Expected: "<<5<<"\n";
  222. cout<<"Recieved: "<< res <<" \n\n";}
  223. cout<<"---------------------------------------------"<<"\n";
  224.  
  225. }
  226. /******************************************************************/
  227.  
  228.  
  229. /***************************Test 4 ********************************/
  230.  
  231. if(Test_No==0 || Test_No==4){
  232. string ABC3[]={"..*E","K*SK"};
  233. maze= new vector<string> (&ABC3[0],&ABC3[2]);
  234. res = tmp.traverseMaze(*maze);
  235. if(res == 2) cout<<"test #"<<4<<" Correct!\n\n";
  236.   else {cout<<"test #"<<4<<" Wrong!\n";
  237. cout<<"Expected: "<<2<<"\n";
  238. cout<<"Recieved: "<< res <<" \n\n";}
  239. cout<<"---------------------------------------------"<<"\n";
  240.  
  241. }
  242. /******************************************************************/
  243.  
  244.  
  245. /***************************Test 5 ********************************/
  246.  
  247. if(Test_No==0 || Test_No==5){
  248. string ABC4[]={".E.KK","*K.S*"};
  249. maze= new vector<string> (&ABC4[0],&ABC4[2]);
  250. res = tmp.traverseMaze(*maze);
  251. if(res == 3) cout<<"test #"<<5<<" Correct!\n\n";
  252.   else {cout<<"test #"<<5<<" Wrong!\n";
  253. cout<<"Expected: "<<3<<"\n";
  254. cout<<"Recieved: "<< res <<" \n\n";}
  255. cout<<"---------------------------------------------"<<"\n";
  256.  
  257. }
  258. /******************************************************************/
  259.  
  260.  
  261. /***************************Test 6 ********************************/
  262.  
  263. if(Test_No==0 || Test_No==6){
  264. string ABC5[]={"*E.**","*..SK","****.","..***"};
  265. maze= new vector<string> (&ABC5[0],&ABC5[4]);
  266. res = tmp.traverseMaze(*maze);
  267. if(res == 3) cout<<"test #"<<6<<" Correct!\n\n";
  268.   else {cout<<"test #"<<6<<" Wrong!\n";
  269. cout<<"Expected: "<<3<<"\n";
  270. cout<<"Recieved: "<< res <<" \n\n";}
  271. cout<<"---------------------------------------------"<<"\n";
  272.  
  273. }
  274. /******************************************************************/
  275.  
  276.  
  277. /***************************Test 7 ********************************/
  278.  
  279. if(Test_No==0 || Test_No==7){
  280. string ABC6[]={".*","EK",".K","S."};
  281. maze= new vector<string> (&ABC6[0],&ABC6[4]);
  282. res = tmp.traverseMaze(*maze);
  283. if(res == 2) cout<<"test #"<<7<<" Correct!\n\n";
  284.   else {cout<<"test #"<<7<<" Wrong!\n";
  285. cout<<"Expected: "<<2<<"\n";
  286. cout<<"Recieved: "<< res <<" \n\n";}
  287. cout<<"---------------------------------------------"<<"\n";
  288.  
  289. }
  290. /******************************************************************/
  291.  
  292.  
  293. /***************************Test 8 ********************************/
  294.  
  295. if(Test_No==0 || Test_No==8){
  296. string ABC7[]={".*.",".**","ES.","...",".KK"};
  297. maze= new vector<string> (&ABC7[0],&ABC7[5]);
  298. res = tmp.traverseMaze(*maze);
  299. if(res == 1) cout<<"test #"<<8<<" Correct!\n\n";
  300.   else {cout<<"test #"<<8<<" Wrong!\n";
  301. cout<<"Expected: "<<1<<"\n";
  302. cout<<"Recieved: "<< res <<" \n\n";}
  303. cout<<"---------------------------------------------"<<"\n";
  304.  
  305. }
  306. /******************************************************************/
  307.  
  308.  
  309. /***************************Test 9 ********************************/
  310.  
  311. if(Test_No==0 || Test_No==9){
  312. string ABC8[]={"...*.","..***","...K*","S*E**"};
  313. maze= new vector<string> (&ABC8[0],&ABC8[4]);
  314. res = tmp.traverseMaze(*maze);
  315. if(res == 4) cout<<"test #"<<9<<" Correct!\n\n";
  316.   else {cout<<"test #"<<9<<" Wrong!\n";
  317. cout<<"Expected: "<<4<<"\n";
  318. cout<<"Recieved: "<< res <<" \n\n";}
  319. cout<<"---------------------------------------------"<<"\n";
  320.  
  321. }
  322. /******************************************************************/
  323.  
  324.  
  325. /***************************Test 10 ********************************/
  326.  
  327. if(Test_No==0 || Test_No==10){
  328. string ABC9[]={".*..","*.K.","KS.*","*KE*"};
  329. maze= new vector<string> (&ABC9[0],&ABC9[4]);
  330. res = tmp.traverseMaze(*maze);
  331. if(res == 2) cout<<"test #"<<10<<" Correct!\n\n";
  332.   else {cout<<"test #"<<10<<" Wrong!\n";
  333. cout<<"Expected: "<<2<<"\n";
  334. cout<<"Recieved: "<< res <<" \n\n";}
  335. cout<<"---------------------------------------------"<<"\n";
  336.  
  337. }
  338. /******************************************************************/
  339.  
  340.  
  341.   return 0;
  342.  
  343. }
  344.  
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!