cses

solution to cses exercise problems
git clone git://git.superpozycja.net/cses
Log | Files | Refs | README

grid_paths.cpp (1451B)

      1 #include <bits/stdc++.h>
      2 
      3 using namespace std;
      4 
      5 using ui = unsigned int;
      6 using l = long;
      7 using ul = unsigned long;
      8 using ll = long long;
      9 using ull = unsigned long long;
     10 
     11 using vi = vector<int>;
     12 using vui = vector<ui>;
     13 using vl = vector<l>;
     14 using vul = vector<ul>;
     15 using vll = vector<ll>;
     16 using vull = vector<ull>;
     17 
     18 int v[7][7];
     19 int p, s;
     20 string path;
     21 
     22 void rec(int r, int c)
     23 {
     24 	if (v[r][c])
     25 		return;
     26 
     27 	if ((r == 0 && v[r+1][c]) || (r == 6 && v[r-1][c]))
     28 		if (c > 0 && c < 6 && !v[r][c-1] && !v[r][c+1])
     29 			return;
     30 
     31 	if ((c == 0 && v[r][c+1]) || (c == 6 && v[r][c-1]))
     32 		if (r > 0 && r < 6 && !v[r-1][c] && !v[r+1][c])
     33 			return;
     34 
     35 	if (r > 0 && r < 6 && v[r+1][c] && v[r-1][c])
     36 		if (c > 0 && c < 6 && !v[r][c-1] && !v[r][c+1])
     37 			return;
     38 
     39 	if (c > 0 && c < 6 && v[r][c+1] && v[r][c-1])
     40 		if (r > 0 && r < 6 && !v[r-1][c] && !v[r+1][c])
     41 			return;
     42 
     43 	if (r == 6 && c == 0) {
     44 		if(s == 48) {
     45 			p++;
     46 		}
     47 		return;
     48 	}
     49 	v[r][c] = 1;
     50 	if (r < 6 && !v[r + 1][c] && (path[s] == 'D' || path[s] == '?')) {
     51 		s++;
     52 		rec(r + 1, c);
     53 		s--;
     54 	}
     55 	if (r > 0 && !v[r - 1][c] && (path[s] == 'U' || path[s] == '?')) {
     56 		s++;
     57 		rec(r - 1, c);
     58 		s--;
     59 	}
     60 	if (c < 6 && !v[r][c + 1] && (path[s] == 'R' || path[s] == '?')) {
     61 		s++;
     62 		rec(r, c + 1);
     63 		s--;
     64 	}
     65 	if (c > 0 && !v[r][c - 1] && (path[s] == 'L' || path[s] == '?')) {
     66 		s++;
     67 		rec(r, c - 1);
     68 		s--;
     69 	}
     70 	v[r][c] = 0;
     71 }
     72 
     73 void solve()
     74 {
     75 	getline(cin, path);
     76 	rec(0, 0);
     77 	cout << p << "\n";
     78 }
     79 
     80 int main()
     81 {
     82 	solve();
     83 }