Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdio.h>
- #include <cstdio>
- #include <algorithm>
- #include <iostream>
- #include <string>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <math.h>
- #include <map>
- #include <set>
- #include <cstdlib>
- #include <utility>
- #include <iomanip>
- #include <cmath>
- using namespace std;
- //#define forn(i,n) for(int i=0;i<n;++i)
- //#define all(v) (v).begin(), (v).end()
- typedef long long ll;
- typedef long double ld;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef pair<double, double> pdd;
- typedef pair<ld, ld> plldd;
- typedef vector<pair<int, int > > vpii;
- int const SIZE = 70, INF = 1e9;
- void files() {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- }
- void fic() {
- //files();
- //setlocale(LC_ALL, "Russian");
- //cout.precision(20);
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- }
- struct edge {
- int from, to, weight;
- edge() {}
- edge(int from, int to, int weight) :
- from(from), to(to), weight(weight) {}
- };
- int n = 8;
- bool exist(int x, int y) {
- if (x < 0 || x >= n || y < 0 || y >= n)
- return false;
- return true;
- }
- int dx[] = { 1, 1, 1, -1, -1, -1, 0, 0 };
- int dy[] = { 0, 1, -1, 0, 1, -1, -1, 1 };
- int size_d = 8;
- int ans, cnt;
- char stx, fx;
- int starty, finishy, startx, finishx;
- //int used[110][110][110];
- queue<pair<pii, int>> q;
- //set<pii>used;
- /*void dfs(int xa, int ya, int time) {
- if (used.count({xa, ya}) || time > cnt || time>64) {
- used.insert({xa, ya});
- return;
- }
- if (time == cnt && ya == finishy && xa == finishx)ans++;
- used.insert({ xa, ya });
- for (int i = 0; i < size_d; i++) {
- int toX = xa + dx[i];
- int toY = ya + dy[i];
- if (exist(toX, toY) && !used.count({ toX, toY })) {
- dfs(toX, toY, time + 1);
- used.erase({ toX, toY });
- }
- }
- cout << ans;
- }*/
- int main() {
- fic();
- ans=0;
- cin >> stx >> starty >> fx >> finishy >> cnt;
- starty--, finishy--;
- startx = stx - 'A';
- finishx = fx - 'A';
- //used[startx][starty][0] = 1;
- set<pair<pii, int>>used;
- used.insert({ { startx, starty }, 0 });
- //dfs(startx, starty, 0);
- q.push({ { startx, starty}, 0 });
- while (!q.empty()) {
- int xa = q.front().first.first;
- int ya = q.front().first.second;
- int cn = q.front().second+1;
- if (cn > cnt)break;
- q.pop();
- for (int i = 0; i < size_d; ++i) {
- int toX = xa + dx[i];
- int toY = ya + dy[i];
- if (exist(toX, toY) /*&& !used.count({ {toX, toY}, cn})*/) {
- q.push({ { toX, toY}, cn });
- used.insert({ {toX, toY}, cn });
- }
- if (toX == finishx && toY == finishy && cn == cnt) {
- ans++;
- }
- //cout << ans<<" "<<cn<<"\n";
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement