⌈HGOI2019/4/8⌋搜索考试解题报告
t1-Flood-it!(floodit)
我们可以发现，每次寻找左上角的格子所在的联通块耗费的时间常数巨大。因此我们在这里寻求突破。
我们引入一个N*N的v数组。左上角的格子所在的联通块里的格子标记为1。左上角联通块周围一圈格子标记为2，其它格子标记为0。如果某次选择了颜色c，我们只需要找出标记为2并且颜色为c的格子，向四周扩展，并相应地修改v标记，就可以不断扩大标记为1的区域，最终如果所有格子标记都是1，那么显然找到了答案。
#include <bits/stdc++.h>
#define ms(a, b) memset(a, b, sizeof(a))
#define ll long long
#define ull unsigned long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
#define Pi acos(-1)
#define eps 1e-8
using namespace std;
template <typename T> void read(T &x) {
x = 0; T fl = 1; char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10); putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) { write(x); puts(""); }
int s,n,mp[9][9],mark[9][9];
int xx[4]={1,-1,0,0},yy[4]={0,0,-1,1},used[6];
bool ans;
int get() {
int t = 0;
memset(used ,0,sizeof(used));
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if (!used[mp[i][j]] && mark[i][j] != 1) {
used[mp[i][j]] = 1;
t ++;
}
return t;
}
void dfs(int a,int b,int x) {
mark[a][b] = 1;
for (int i = 0; i < 4; i ++) {
int nowx = a + xx[i] , nowy = b + yy[i];
if (nowx<1||nowy<1||nowx>n||nowy>n||mark[nowx][nowy]==1)continue;
mark[nowx][nowy] = 2;
if(mp[nowx][nowy] == x)dfs(nowx,nowy,x);
}
}
int fill(int x) {
int t = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if(mark[i][j] == 2 && mp[i][j] == x) {
t ++;
dfs(i, j, x);
}
return t;
}
void search(int k) {
int v = get();
if (!v)ans=1;
if (k + v > s || ans)return;
int temp[10][10];
for (int i = 0; i <= 5; i ++) {
memcpy(temp,mark,sizeof(mark));
if(fill(i)) search(k+1);
memcpy(mark, temp, sizeof(mark));
}
}
int main() {
while(1) {
memset(mark,0,sizeof(mark));
read(n);
ans = 0;
if (n == 0) break;
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) read(mp[i][j]);
dfs(1,1,mp[1][1]);
for(s=0;;s++) { search(0); if(ans){printf("%d\n",s);break;}}
}
return 0;
}t2-八数码难题
这道题可以之间把unsolve的情况处理出来，因为A*全部遍历非常的慢。
结论：除了0以外的格子，拉平之后逆序对的个数是奇数则unsolve。
剩下来的就是A*的正常操作了。
#include <bits/stdc++.h>
using namespace std;
struct rec{
int state,dist;
rec(){}
rec(int s,int d){state=s,dist=d;}
};
int a[3][3];
map<int,int> d,f,go;
priority_queue<rec> q;
const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
char dir[4]={'u','l','r','d'};
int kkk[105];
bool operator <(rec a,rec b) { return a.dist>b.dist; }
int calc(int a[3][3]) {
int val=0;
for(int i=0;i<3;i++) for(int j=0;j<3;j++) { val=val*9+a[i][j]; }
return val;
}
pair<int,int> recover(int val,int a[3][3]) {
int x,y;
for(int i=2;i>=0;i--)
for(int j=2;j>=0;j--) {
a[i][j]=val%9;
val/=9;
if(a[i][j]==0) x=i,y=j;
}
return make_pair(x,y);
}
int value(int a[3][3]) {
int val=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++) {
if(a[i][j]==0) continue;
int x=(a[i][j]-1)/3;
int y=(a[i][j]-1)%3;
val+=abs(i-x)+abs(j-y);
}
return val;
}
int astar(int sx,int sy,int e) {
d.clear(); f.clear(); go.clear();
while(q.size()) q.pop();
int start=calc(a);
d[start]=0;
q.push(rec(start,0+value(a)));
while(q.size()) {
int now=q.top().state; q.pop();
if(now==e) return d[now];
int a[3][3];
pair<int,int> space=recover(now,a);
int x=space.first,y=space.second;
for(int i=0;i<4;i++) {
int nx=x+dx[i], ny=y+dy[i];
if (nx<0||nx>2||ny<0||ny>2) continue;
swap(a[x][y],a[nx][ny]);
int next=calc(a);
if(d.find(next)==d.end()||d[next]>d[now]+1) {
d[next]=d[now]+1;
f[next]=now;
go[next]=i;
q.push(rec(next,d[next]+value(a)));
}
swap(a[x][y],a[nx][ny]);
}
}
return -1;
}
void print(int e) {
if(f.find(e)==f.end()) return;
print(f[e]);
putchar(dir[go[e]]);
}
int main() {
int x,y; char str[2];
while (scanf("%s", str) != EOF) {
int cnt=0,sum=0;
d.clear(); f.clear(); go.clear();
while (!q.empty()) q.pop();
if(str[0]=='x') a[0][0]=0,x=0,y=0; else kkk[++ cnt]=a[0][0]=str[0]-'0';
int end=0;
for(int i=1;i<=8;i++) end=end*9+i;
end*=9;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++) {
if (i == 0 && j == 0) continue;
scanf("%s",str);
if(str[0]=='x') a[i][j]=0,x=i,y=j;
else kkk[++ cnt]=a[i][j]=str[0]-'0';
}
for (int i = 1; i <= cnt; i ++)
for(int j=cnt;j>i;j--){
if(kkk[j]<kkk[j-1])swap(kkk[j],kkk[j-1]),sum++;
}
if (sum % 2 == 1) { printf("unsolvable\n"); continue; }
int ans=astar(x,y,end);
if(ans==-1) puts("unsolvable");
else print(end), puts("");
}
return 0;
}t3-电路维修
简单建图跑最短路。
#include <bits/stdc++.h>
#define ms(a, b) memset(a, b, sizeof(a))
#define ll long long
#define ull unsigned long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
#define Pi acos(-1)
#define eps 1e-8
#define N 505
using namespace std;
template <typename T> void read(T &x) {
x = 0; T fl = 1; char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10); putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) { write(x); puts(""); }
struct edge {
int to, nt, w;
} E[4 * N * N + 5];
int dis[N * N + 5], H[N * N + 5], vis[N * N + 5];
int cnt, n, m;
char s[N];
struct Node {
int u, Dist;
bool operator <(const Node &rhs) const { return Dist > rhs.Dist; }
};
priority_queue<Node> q;
void add_edge(int u, int v, int w) {
E[++ cnt] = (edge){v, H[u], w};
H[u] = cnt;
}
void Dijkstra(int s) {
ms(vis, 0);
ms(dis, inf);
while (!q.empty()) q.pop();
q.push((Node){s, 0});
dis[s] = 0;
while (!q.empty()) {
Node cur = q.top(); q.pop(); int u = cur.u;
if (vis[cur.u]) continue;
vis[cur.u] = 1;
for (int e = H[u]; e; e = E[e].nt) {
int v = E[e].to, w = E[e].w;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) q.push((Node){v, dis[v]});
}
}
}
}
int main() {
int cas; read(cas);
while (cas --) {
cnt = 0; ms(H, 0); ms(E, 0);
read(n); read(m);
for (int i = 1; i <= n; i ++) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j ++) {
int x1 = (i - 1) * (m + 1) + j, x2 = (i - 1) * (m + 1) + j + 1, x3 = i * (m + 1) + j, x4 = i * (m + 1) + j + 1;
if (s[j] == '/') add_edge(x1, x4, 1), add_edge(x4, x1, 1), add_edge(x2, x3, 0), add_edge(x3, x2, 0);
else add_edge(x2, x3, 1), add_edge(x3, x2, 1), add_edge(x1, x4, 0), add_edge(x4, x1, 0);
}
}
Dijkstra(1);
if (dis[(n + 1) * (m + 1)] == inf) puts("NO SOLUTION");
else writeln(dis[(n + 1) * (m + 1)]);
}
return 0;
}
t4-The Rotation Game 拉链游戏
\(IDA^*\)算法
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#pragma GCC optimize(2)
#define ms(a, b) memset(a, b, sizeof(a))
#define ll long long
#define ull unsigned long long
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f
#define db double
#define Pi acos(-1)
#define eps 1e-8
#define BASE 217
using namespace std;
template <typename T> void read(T &x) {
x = 0; T fl = 1; char ch = 0;
for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') fl = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
x *= fl;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10); putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) { write(x); puts(""); }
const int g[8][7] = { {0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10}
};
const int center[8] = {6, 7, 8, 12, 17, 16, 15, 11};
int a[24], res[1005], ans, MAX_DEP;
int cal() {
int cnt[3] = {0,0,0};
for (int i = 0; i < 8; i ++) cnt[a[center[i]] - 1] ++;
return 8 - max(cnt[0], max(cnt[1], cnt[2]));
}
void change(int pos) {
int tmp = a[g[pos][0]];
for (int i = 1; i < 7; i ++) a[g[pos][i - 1]] = a[g[pos][i]];
a[g[pos][6]] = tmp;
}
bool dfs(int dep) {
int tmp[24];
memcpy(tmp, a, sizeof(a));
for (int i = 0; i < 8; i ++) {
change(i);
int t = cal();
if (t == 0) {
res[dep] = i;
ans = a[center[0]];
return 1;
}
if (dep + t <= MAX_DEP) if (dfs(dep + 1)) {
res[dep] = i;
return 1;
}
memcpy(a, tmp, sizeof(a));
}
return 0;
}
int main() {
scanf("%d", &a[0]);
while (a[0] != 0) {
for (int i = 1; i < 24; i ++) read(a[i]);
MAX_DEP = cal();
if (MAX_DEP == 0) {
printf("No moves needed\n%d\n", a[6]);
scanf("%d", &a[0]);
continue;
}
while (!dfs(1)) MAX_DEP ++;
for (int i = 1; i <= MAX_DEP; i ++) printf("%c", res[i] + 'A');
printf("\n%d\n", ans); scanf("%d", &a[0]);
}
return 0;
}
更多精彩
