Ural 1298 Knight 题解
程序员文章站
2022-06-19 19:08:16
Ural 1298 Knight 题解 [TOC] 题意 给定一个$n\times n(1\le n\le8)$的国际象棋棋盘和一个骑士(基本上相当于中国象棋的马),问可否用经过每个格子$1$次。如果可以,输出路径,否则输出 。 题解 考虑回溯。暴力程序十分好写,但是会超时。 可以用启发式优化。 设 ......
ural 1298 knight 题解
题意
给定一个\(n\times n(1\le n\le8)\)的国际象棋棋盘和一个骑士(基本上相当于中国象棋的马),问可否用经过每个格子\(1\)次。如果可以,输出路径,否则输出impossible
。
题解
考虑回溯。暴力程序十分好写,但是会超时。
可以用启发式优化。
设当前点为\((x,y)\),可到达的点为\((x',y')\)。优先选择\((x',y')\)状态种数少的回溯,即可以转移的格子的数量少。
这样优化后就可以过了。
tip: 优化后很快,为\(0.015s\)。
程序
// #pragma gcc optimize(2) // #pragma g++ optimize(2) // #pragma comment(linker,"/stack:102400000,102400000") // #include <bits/stdc++.h> #include <map> #include <set> #include <list> #include <array> #include <cfenv> #include <cmath> #include <ctime> #include <deque> #include <mutex> #include <queue> #include <ratio> #include <regex> #include <stack> #include <tuple> #include <atomic> #include <bitset> #include <cctype> #include <cerrno> #include <cfloat> #include <chrono> #include <cstdio> #include <cwchar> #include <future> #include <limits> #include <locale> #include <memory> #include <random> #include <string> #include <thread> #include <vector> #include <cassert> #include <climits> #include <clocale> #include <complex> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdlib> #include <cstring> #include <ctgmath> #include <cwctype> #include <fstream> #include <iomanip> #include <numeric> #include <sstream> #include <ccomplex> #include <cstdbool> #include <iostream> #include <typeinfo> #include <valarray> #include <algorithm> #include <cinttypes> #include <cstdalign> #include <stdexcept> #include <typeindex> #include <functional> #include <forward_list> #include <system_error> #include <unordered_map> #include <unordered_set> #include <scoped_allocator> #include <condition_variable> // #include <conio.h> // #include <windows.h> using namespace std; typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef float fl; typedef double ld; typedef long double ld; typedef pair<int,int> pii; #if (win32) || (win64) || (__win32) || (__win64) || (_win32) || (_win64) || (windows) #define lld "%i64d" #define llu "%i64u" #else #define lld "%lld" #define llu "%llu" #endif #define ui(n) ((unsigned int)(n)) #define ll(n) ((long long)(n)) #define ull(n) ((unsigned long long)(n)) #define fl(n) ((float)(n)) #define ld(n) ((double)(n)) #define ld(n) ((long double)(n)) #define char(n) ((char)(n)) #define bool(n) ((bool)(n)) #define fixpoint(n) fixed<<setprecision(n) const int inf=1061109567; const int ninf=-1044266559; const ll linf=4557430888798830399; const ld eps=1e-15; #define mod (1000000007) #define pi (3.1415926535897932384626433832795028841971) /* #define mb_len_max 5 #define shrt_min (-32768) #define shrt_max 32767 #define ushrt_max 0xffffu #define int_min (-2147483647 - 1) #define int_max 2147483647 #define uint_max 0xffffffffu #define long_min (-2147483647l - 1) #define long_max 2147483647l #define ulong_max 0xfffffffful #define llong_max 9223372036854775807ll #define llong_min (-9223372036854775807ll - 1) #define ullong_max 0xffffffffffffffffull */ #define mp make_pair #define mt make_tuple #define all(a) (a).begin(),(a).end() #define pall(a) (a).rbegin(),(a).rend() #define log2(x) log(x)/log(2) #define log(x,y) log(x)/log(y) #define sz(a) ((int)(a).size()) #define rep(i,n) for(int i=0;i<((int)(n));i++) #define rep1(i,n) for(int i=1;i<=((int)(n));i++) #define repa(i,a,n) for(int i=((int)(a));i<((int)(n));i++) #define repa1(i,a,n) for(int i=((int)(a));i<=((int)(n));i++) #define repd(i,n) for(int i=((int)(n))-1;i>=0;i--) #define repd1(i,n) for(int i=((int)(n));i>=1;i--) #define repda(i,n,a) for(int i=((int)(n));i>((int)(a));i--) #define repda1(i,n,a) for(int i=((int)(n));i>=((int)(a));i--) #define for(i,a,n,step) for(int i=((int)(a));i<((int)(n));i+=((int)(step))) #define repv(itr,v) for(__typeof((v).begin()) itr=(v).begin();itr!=(v).end();itr++) #define repv(i,v) for(auto i:v) #define repe(i,v) for(auto &i:v) #define ms(x,y) memset(x,y,sizeof(x)) #define mc(x) ms(x,0) #define minf(x) ms(x,63) #define mcp(x,y) memcpy(x,y,sizeof(y)) #define sqr(x) ((x)*(x)) #define un(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define filein(x) freopen(x,"r",stdin) #define fileout(x) freopen(x,"w",stdout) #define fileio(x)\ freopen(x".in","r",stdin);\ freopen(x".out","w",stdout) #define filein2(filename,name) ifstream name(filename,ios::in) #define fileout2(filename,name) ofstream name(filename,ios::out) #define file(filename,name) fstream name(filename,ios::in|ios::out) #define pause system("pause") #define cls system("cls") #define fs first #define sc second #define pc(x) putchar(x) #define gc(x) x=getchar() #define endl pc('\n') #define sf scanf #define pf printf inline int read() { int x=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');} inline ll powmod(ll a,ll b){ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;} inline ll gcdll(ll a,ll b){return b?gcdll(b,a%b):a;} const int dx[]={1,1,2,2,-1,-1,-2,-2}; const int dy[]={2,-2,1,-1,2,-2,1,-1}; /************************************************************begin************************************************************/ const int maxn=10; int n,cnt[maxn][maxn]; bool vis[maxn][maxn]; pair<int,int> pre[maxn][maxn]; vector<pair<int,int> > v; inline bool ok() { rep(i,n) rep(j,n) if(!vis[i][j]) return 0; return 1; } inline void print(int x,int y) { if(pre[x][y].fs!=-1) print(pre[x][y].fs,pre[x][y].sc); pf("%c%c\n",char(x+'a'),char(y+'1')); } inline bool cmp(pair<int,int> x,pair<int,int> y) { return cnt[x.fs][x.sc]<cnt[y.fs][y.sc]; } inline void dfs(int x,int y) { vis[x][y]=1; if(ok()) { print(x,y); exit(0); } vector<pair<int,int> > w;w.clear(); rep(i,8) { int cx=x+dx[i],cy=y+dy[i]; if(cx>=0&&cx<n&&cy>=0&&cy<n&&!vis[cx][cy]) w.push_back({cx,cy}); } sort(all(w),cmp); repv(i,w) { int cx=i.fs,cy=i.sc; pre[cx][cy]={x,y}; dfs(cx,cy); } vis[x][y]=0; } int main() { sf("%d",&n); rep(i,n) rep(j,n) { v.push_back({i,j}); rep(k,8) { int ci=i+dx[k],cj=j+dy[k]; if(ci>=0&&ci<n&&cj>=0&&cj<n) cnt[i][j]++; } } sort(all(v),cmp); repv(it,v) { int i=it.fs,j=it.sc; mc(vis); mc(pre); pre[i][j]={-1,-1}; dfs(i,j); } pf("impossible"); return 0; } /*************************************************************end**************************************************************/
上一篇: 她是曹操妻妾,勾搭亲卫却没被杀死
下一篇: C++多线程基础学习笔记(十)