[2020.12.21
]
自从上个礼拜打铁以来，感觉整个人都不对劲。
最近几天打了一些比赛，找回了一点感觉。
这段时间到考试前，我打算刷一刷kuangbin题单，毕竟这是开学的时候就立下的Flag...
...只完成了最后一个不用脑子的...
实在是太草了
一、 搜索专题
A - 棋盘问题
#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
int n, k, ans;
char mp[10][10];
int col[10];
void dfs(int now,int sum){
if(sum == k){
ans++;return;
}
if (now > n)return;
for(int i = 1;i <= n;i++){
if(mp[now][i] == '#' and !col[i]){
col[i] = 1;
dfs(now + 1, sum + 1);
col[i] = 0;
}
}
dfs(now + 1, sum);
}
int main(){
while(~scanf("%d%d",&n,&k) and n != -1){
for (int i = 1;i <= n;i++) scanf("%s", mp[i] + 1);
ans = 0;
dfs(0, 0);
printf("%d
", ans);
}
}
B - Dungeon Master
三维迷宫bfs，我属实有点拉跨了。
我开始一直MLE还埋怨是不是poj的问题，后来发现自己bfs没有开vis数组...
后来输出的时候没有加
.（一个优雅的英文句号） ...
/*
* @Author: zhl
* @LastEditTime: 2020-12-21 15:01:56
*/
#include<cstdio>
#include<queue>
using namespace std;
int h, n, m;
char mp[40][40][40];
typedef struct {
int h, x, y;
}p;
const int dh[] = { 1,-1,0,0,0,0 };
const int dx[] = { 0,0,1,-1,0,0 };
const int dy[] = { 0,0,0,0,1,-1 };
p st, ed;
int main() {
while (scanf("%d%d%d", &h, &n, &m) and h != 0) {
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= n; j++) {
scanf("%s", mp[i][j] + 1);
for (int k = 1; k <= m; k++) {
if (mp[i][j][k] == 'S')st = { i,j,k };
if (mp[i][j][k] == 'E')ed = { i,j,k };
}
}
}
queue<p>Q; Q.push(st);
int ans = -1, now = 0;
while (not Q.empty()) {
int sz = Q.size();
while (sz--) {
p tp = Q.front(); Q.pop();
if (tp == ed) {
ans = now;
goto END;
}
for (int i = 0; i < 6; i++) {
int nh = tp.h + dh[i];
int nx = tp.x + dx[i];
int ny = tp.y + dy[i];
if (nh > h or nh < 1 or nx > n or nx < 1 or ny > m or ny < 1)continue;
if (mp[nh][nx][ny] == '#')continue;
Q.push({ nh,nx,ny });
}
}
now++;
}
END:
if (ans == -1)puts("Trapped!");
else printf("Escaped in %d minute(s).
", ans);
}
}
C - Catch That Cow
/*
* @Author: zhl
* @LastEditTime: 2020-12-21 15:19:05
*/
#include<cstdio>
#include<queue>
using namespace std;
int n, k;
int vis[100010];
int main() {
scanf("%d%d", &n, &k);
queue<int>Q; Q.push(n); vis[n] = 1;
int ans = 0;
while (not Q.empty()) {
int sz = Q.size();
while (sz--) {
int tp = Q.front(); Q.pop();
if (tp == k) {
printf("%d
", ans);
return 0;
}
if (tp > 0 and !vis[tp - 1])vis[tp - 1] = 1, Q.push(tp - 1);
if (tp < 100009 and !vis[tp + 1])vis[tp + 1] = 1, Q.push(tp + 1);
if (tp * 2 < 100010 and !vis[tp * 2])vis[tp * 2] = 1, Q.push(2 * tp);
}
ans++;
}
puts("-1");
}
D - Fliptile
很垃圾的一份代码，只有一个剪枝。
代码也写的没法看...
我不应该瞧不起这些题目...
其实好像第一行确定了方案就确定了，好像可以暴力枚举第一行
好像也差不多
/*
* @Author: zhl
* @LastEditTime: 2020-12-21 15:33:28
* @res: 641ms / limit 2000ms
*/
#include<cstdio>
bool flag;
int mp[20][20], n, m;
const int dx[] = { 1,0,-1,0,0 };
const int dy[] = { 0,1,0,-1,0 };
int ans[20][20], res[20][20], mx;
void dfs(int x, int y,int sum) {
if (x > n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)if (mp[i][j] == 1)return;
}
flag = true;
if (sum < mx) {
mx = sum;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
res[i][j] = ans[i][j];
//printf("%d%c", ans[i][j], "
"[j == m]);
}
}
}
else if (sum == mx) {
bool le = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (ans[i][j] > res[i][j])le = false;
}
}
if (le) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
res[i][j] = ans[i][j];
//printf("%d%c", ans[i][j], "
"[j == m]);
}
}
}
}
return;
}
if (x > 1) {
if (mp[x - 1][y] == 0) {
//if (x == n and y > 1 and mp[x][y - 1] == 1)return;
ans[x][y] = 0, dfs(x + (y == m), (y == m) ? 1 : y + 1, sum);
}
else {
//if (x == n && y > 1 && mp[x][y - 1] == 0)return;
ans[x][y] = 1;
for (int i = 0; i < 5; i++)mp[x + dx[i]][y + dy[i]] ^= 1;
dfs(x + (y == m), (y == m) ? 1 : y + 1, sum + 1);
for (int i = 0; i < 5; i++)mp[x + dx[i]][y + dy[i]] ^= 1;
}
}
else {
ans[x][y] = 0;
dfs(x + (y == m), (y == m) ? 1 : y + 1, sum);
ans[x][y] = 1;
for (int i = 0; i < 5; i++)mp[x + dx[i]][y + dy[i]] ^= 1;
dfs(x + (y == m), (y == m) ? 1 : y + 1, sum + 1);
for (int i = 0; i < 5; i++)mp[x + dx[i]][y + dy[i]] ^= 1;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)scanf("%1d", mp[i] + j);
mx = 1000000;
dfs(1, 1, 0);
if (!flag)puts("IMPOSSIBLE");
else {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
//res[i][j] = ans[i][j];
printf("%d%c", res[i][j], "
"[j == m]);
}
}
}
}
我一番压行操作后
我悟出一个道理
在DFS的时候，在进入dfs前剪枝和进入dfs后再剪枝是不一样的，前则要快不少。
/*
* @Author: zhl
* @LastEditTime: 2020-12-21 15:59:09
* @res: 782ms / limit: 2000ms
*/
#include<cstdio>
#define max(a,b) (a>b?a:b)
bool flag;
int mp[20][20], n, m;
const int dx[] = { 1,0,-1,0,0 };
const int dy[] = { 0,1,0,-1,0 };
int ans[20][20], res[20][20], mx;
void dfs(int x, int y, int sum) {
if (x > n) {
if (sum > mx)return;
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)if (mp[i][j] == 1 || (sum == mx && (ans[i][j] > res[i][j])))return;
flag = true; mx = sum;
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)res[i][j] = ans[i][j];
return;
}
if(x == 1 || mp[x-1][y] == 0)ans[x][y] = 0,dfs(x + (y == m), (y == m) ? 1 : y + 1, sum);
if (x == 1 || mp[x - 1][y] == 1) {
for (int i = 0; i < 5; i++)mp[x + dx[i]][y + dy[i]] ^= 1;
ans[x][y] = 1;
dfs(x + (y == m), (y == m) ? 1 : y + 1, sum + 1);
for (int i = 0; i < 5; i++)mp[x + dx[i]][y + dy[i]] ^= 1;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)scanf("%1d", mp[i] + j);
mx = 751404976; dfs(1, 1, 0);
if (!flag)puts("IMPOSSIBLE");
else {
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)printf("%d%c", res[i][j], "
"[j == m]);
}
}
E - Find The Multiple
暴力算了一些数据发现位数都比较小，于是直接从低位搜到高位。
裸的搜索可以直接交上去，跑了 938ms
发现 m == 198 的时候搜的答案是 1111111111111111110，可以直接加个特判。
跑了 344ms
当然也可以直接打表光速过题。
#include<cstdio>
/* status : 938ms / 1000ms */
using namespace std;
typedef long long ll;
ll ans[300];
ll get(ll j) {
if (ans[j])return ans[j];
for (int i = 1;i < 1 << 20;i++) {
ll base = 1, now = 0;
for (int k = 0;k < 20;k++) {
if ((i >> k) & 1)now = (now + base) % j;
base = base * 10 % j;
}
if (now == 0)return ans[j] = i;
}
}
void print(ll x) {
if (!x)return;
print(x >> 1);
if (x & 1)putchar('1');else putchar('0');
}
int main() {
int n;
while (scanf("%d", &n) && n > 0) {
print(get(n));puts("");
}
}
#include<cstdio>
/* 加了特判 status: 344ms / 1000ms */
using namespace std;
typedef long long ll;
ll ans[300];
ll get(ll j) {
if (ans[j])return ans[j];
for (int i = 1; i < 1 << 19; i++) {
ll base = 1, now = 0;
for (int k = 0; k < 19; k++) {
if ((i >> k) & 1)now = (now + base) % j;
base = base * 10 % j;
}
if (now == 0)return ans[j] = i;
}
}
void print(ll x) {
if (!x)return;
print(x >> 1);
if (x & 1)putchar('1'); else putchar('0');
}
int main() {
int n;
while (scanf("%d", &n) && n > 0) {
if (n == 198) {
puts("1111111111111111110"); continue;
}
print(get(n)); puts("");
}
}
F - Prime Path
简单bfs，先建边就可以
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
using namespace std;
bool judge(int x) {
for (int i = 2; i * i <= x; i++)if (x % i == 0)return false;
return true;
}
bool ok(int x, int y) {
int dif = 0;
for (int i = 0; i < 4; i++) {
if (x % 10 != y % 10)dif++;
x /= 10; y /= 10;
}
return dif == 1;
}
int T, x, y;
map<int, vector<int> >G;
int main() {
vector<int>L;
for (int i = 1000; i <= 9999; i++) {
if (judge(i))L.push_back(i);
}
int n = L.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (ok(L[i], L[j])) {
G[L[i]].push_back(L[j]);
G[L[j]].push_back(L[i]);
}
}
}
scanf("%d", &T);
while (T--) {
scanf("%d%d", &x, &y);
queue<int>Q;
int ans = -1, now = 0;
Q.push(x); map<int, int>vis; vis[x] = 1;
while (!Q.empty()) {
int sz = Q.size();
while (sz--) {
int tp = Q.front(); Q.pop();
if (tp == y) {
ans = now;
break;
}
for (int i = 0; i < G[tp].size();i++) {
int v = G[tp][i];
if (!vis[v]) {
Q.push(v);
vis[v] = 1;
}
}
}
if (ans != -1)break;
now++;
}
if (ans == -1)puts("Impossible");
else {
printf("%d
", ans);
}
}
}
G - Shuffle'm Up
直接模拟就可以，注意要手动加一个 ' '
/*
* @Author: zhl
* @LastEditTime: 2020-12-22 09:57:16
*/
#include<cstdio>
#include<cstring>
int T, n;
char s[200], p[200], tm[300], st[300], ed[300];
int main() {
scanf("%d", &T); int c = 0;
while (T--) {
scanf("%d", &n);
scanf("%s", s + 1);
scanf("%s", p + 1);
scanf("%s", ed + 1);
for (int i = 1; i <= n; i++) {
st[2 * i - 1] = p[i];
st[2 * i] = s[i];
}
st[2 * n + 1] = 0; //!!!
strcpy(tm + 1, st + 1);
int ans = -1, now = 1;
while (1) {
for (int i = 1; i <= n; i++) {
s[i] = tm[i]; p[i] = tm[i + n];
}
if (!strcmp(tm + 1, ed + 1)) {
ans = now;
break;
}
if (!strcmp(tm + 1, st + 1) && now != 1) {
break;
}
for (int i = 1; i <= n; i++) {
tm[2 * i - 1] = p[i];
tm[2 * i] = s[i];
}
now++;
}
printf("%d %d
", ++c, ans);
}
}
H - Pots
刚开始以为会很难写，其实细细想一想实现起来也不是特别难。
比较锻炼代码能力
/*
* @Author: zhl
* @LastEditTime: 2020-12-22 19:27:20
*/
#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#define min(a,b) (a<b?a:b)
using namespace std;
int A, B, C;
struct st {
int a, b;
st() {}
st(int _a, int _b) { a = _a, b = _b; }
bool operator < (const st& x)const {
if (a != x.a)return a < x.a;
return b < x.b;
}
}ed;
int vis[200][200];
map<st, st>pre;
char pre_op[200][200][200];
const char op[6][200] = {
"FILL(1)","FILL(2)","DROP(1)",
"DROP(2)","POUR(1,2)","POUR(2,1)"
};
st res[6];
void operate(st x) {
res[0] = st(A, x.b); res[1] = st(x.a, B);
res[2] = st(0, x.b); res[3] = st(x.a, 0);
int mx = min(x.a, B - x.b); res[4] = st(x.a - mx, x.b + mx);
mx = min(A - x.a, x.b); res[5] = st(x.a + mx, x.b - mx);
}
void print(st x) {
if (x.a == 0 and x.b == 0)return;
print(pre[x]);
printf("%s
", pre_op[x.a][x.b]);
}
int main() {
scanf("%d%d%d", &A, &B, &C);
queue<st>Q;
Q.push({ 0,0 }); vis[0][0] = 1;
int ans = -1, now = 0;
while (not Q.empty()) {
int sz = Q.size();
while (sz--) {
st tp = Q.front(); Q.pop();
//printf("(%d , %d)
", tp.a, tp.b);
if (tp.a == C or tp.b == C) {
ans = now;
ed = tp;
break;
}
operate(tp);
for (int i = 0; i < 6; i++) {
if (vis[res[i].a][res[i].b])continue;
vis[res[i].a][res[i].b] = 1;
pre[res[i]] = tp;
strcpy(pre_op[res[i].a][res[i].b], op[i]);
Q.push(res[i]);
}
}
if (ans != -1)break;
now++;
}
if (ans == -1)puts("impossible");
else {
printf("%d
", ans);
print(ed);
}
}
I - Fire Game
看到数据量这么小，脑子里不要带东西。
直接用最裸的暴力就可以了，不需要任何优化
/*
* @Author: zhl
* @LastEditTime: 2020-12-22 20:00:09
*/
#include<cstdio>
#include<queue>
#include<cstring>
#define min(a,b) (a<b?a:b)
using namespace std;
int T, n, m;
char mp[20][20];
struct point {
int x, y;
point() {}
point(int _x, int _y) {
x = _x, y = _y;
}
};
int vis[20][20];
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
int cal(point st1, point st2) {
int ans = 0; memset(vis, 0, sizeof vis);
queue<point>Q; Q.push(st1); Q.push(st2);
vis[st1.x][st1.y] = vis[st2.x][st2.y] = 1;
while (!Q.empty()) {
int sz = Q.size();
while (sz--) {
point tp = Q.front(); Q.pop();
for (int i = 0; i < 4; i++) {
int nx = tp.x + dx[i], ny = tp.y + dy[i];
if (nx < 1 or nx > n or ny < 1 or ny > m or mp[nx][ny] != '#' or vis[nx][ny])continue;
vis[nx][ny] = 1;
Q.push(point(nx, ny));
}
}ans++;
}
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)if (mp[i][j] == '#' and !vis[i][j])return 0x3f3f3f3f;
return ans - 1;
}
int main() {
scanf("%d", &T); int c = 0;
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%s", mp[i] + 1);
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mp[i][j] != '#')continue;
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= m; y++) {
if (mp[x][y] != '#')continue;
ans = min(ans, cal(point(i, j), point(x, y)));
}
}
}
}
if (ans == 0x3f3f3f3f)ans = -1;
printf("Case %d: %d
", ++c, ans);
}
}
J - Fire!
先bfs出每个点到火源的距离，再对joe进行bfs一次，若距离joe的距离大于等于到火的距离则不能入队，看能否到达边缘就可以，Uva挂了不知道对没对
/*
* @Author: zhl
* @LastEditTime: 2020-12-23 10:41:10
*/
#include<bits/stdc++.h>
using namespace std;
int T, n, m;
char mp[1010][1010];
struct p {
int x, y;
};
p fire, joe;
//map<p, int>dis, vis;
int dis[1010][1010], vis[1010][1010];
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
queue<p>Q;
memset(dis, 0, sizeof dis);
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; i++) {
scanf("%s", mp[i] + 1);
for (int j = 1; j <= m; j++) {
if (mp[i][j] == 'J')joe = { i,j };
if (mp[i][j] == 'F')Q.push({ i,j }), vis[i][j] = 1;
}
}
while (not Q.empty()) {
int sz = Q.size();
while (sz--) {
p tp = Q.front(); Q.pop();
for (int i = 0; i < 4; i++) {
int nx = tp.x + dx[i], ny = tp.y + dy[i];
if (nx < 1 or nx > n or ny < 1 or ny > m or mp[nx][ny] == '#' or vis[nx][ny])continue;
vis[nx][ny] = 1;
dis[nx][ny] = dis[tp.x][tp.y] + 1;
Q.push({ nx,ny });
}
}
}
int ans = -1, now = 0;
Q.push(joe); memset(vis,0,sizeof vis); vis[joe.x][joe.y] = 1;
while (not Q.empty()) {
int sz = Q.size();
while (sz--) {
p tp = Q.front(); Q.pop();
if (tp.x == 1 or tp.x == n or tp.y == 1 or tp.y == m) {
ans = now;
break;
}
for (int i = 0; i < 4; i++) {
int nx = tp.x + dx[i], ny = tp.y + dy[i];
if (mp[nx][ny] == '#' or (dis[nx][ny] != 0 and now + 1 >= dis[nx][ny]) or vis[nx][ny])continue;
vis[nx][ny] = 1;
Q.push({ nx,ny });
}
}
if (ans != -1)break;
now++;
}
if (ans == -1)puts("IMPOSSIBLE");
else printf("%d
", ans + 1);
}
}
K - 迷宫问题
这个题我开始觉得太水了，不想写，结果debug，滴了半个多小时
且听我细细道来
对于样例
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
我在下面的代码片加了断点，发现当 nxt == {3,2} 的时候，被 continue 略过去了
我开始改成了 vis.count(nxt) 发现没啥变化，我把 vis[nxt] 去掉，就没有被略过去
int nx = tp.x + dx[i], ny = tp.y + dy[i];
p nxt = { nx,ny };
if (nx < 1 or nx > 5 or ny < 1 or ny > 5 or mz[nx][ny] == 1 or vis[nxt])continue;
后来我一想，原来是重载的问题
bool operator < (const point& b)const {
//return x < b.x;
return x == b.x ? y < b.y : x < b.x;
}
注释掉的是最开始的，因为最开始的时候map报错了，我意识到是要重载运算符，我就随便重载了一下。
队友说是要满足自反性
/*
* @Author: zhl
* @LastEditTime: 2020-12-22 10:51:10
*/
#include<cstdio>
#include<map>
#include<queue>
using namespace std;
int mz[10][10];
typedef struct point {
int x, y;
bool operator == (point b) {
return x == b.x and y == b.y;
}
bool operator < (const point& b)const {
//return x < b.x;
return x == b.x ? y < b.y : x < b.x;
}
}p;
p st, ed;
map<p, p>pre;
map<p, int>vis;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
void print(p x) {
if (x == st) {
printf("(%d, %d)
", x.x - 1, x.y - 1);
return;
}
print(pre[x]);
printf("(%d, %d)
", x.x - 1, x.y - 1);
}
int main() {
for (int i = 1; i <= 5; i++)for (int j = 1; j <= 5; j++)scanf("%d", mz[i] + j);
st = { 1,1 }, ed = { 5,5 };
queue<p>Q; Q.push(st); vis[st] = 1;
while (not Q.empty()) {
p tp = Q.front(); Q.pop();
if (tp == ed) {
break;
}
for (int i = 0; i < 4; i++) {
int nx = tp.x + dx[i], ny = tp.y + dy[i];
p nxt = { nx,ny };
if (nx < 1 or nx > 5 or ny < 1 or ny > 5 or mz[nx][ny] == 1 or vis.count(nxt) == 1)continue;
vis[nxt] = 1;
pre[nxt] = tp;
Q.push(nxt);
//printf("%d %d
", nxt.x, nxt.y);
}
}
print(ed);
}
L - Oil Deposits
用个并查集暴力就可以
/*
* @Author: zhl
* @LastEditTime: 2020-12-22 17:57:53
*/
#include<cstdio>
#include<set>
#define and &&
#define or ||
using namespace std;
int n, m;
char mp[200][200];
int fa[20000];
int find(int a) {
return a == fa[a] ? a : fa[a] = find(fa[a]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x != y)fa[x] = y;
}
int getid(int x, int y) {
return (x - 1) * m + y;
}
const int dx[] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[] = { 0,1,1,1,0,-1,-1,-1 };
int main() {
while (scanf("%d%d", &n, &m) and n) {
for (int i = 1; i <= n; i++) {
scanf("%s", mp[i] + 1);
}
for (int i = 1; i <= n * m; i++)fa[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k < 8; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (mp[i][j] != '@' or nx < 1 or nx > n or ny < 1 or ny > m or mp[nx][ny] != '@')continue;
merge(getid(i, j), getid(nx, ny));
}
}
}
set<int>s;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '@')s.insert(find(getid(i, j)));
}
}
printf("%d
", s.size());
}
}
M - 非常可乐
直接暴力
/*
* @Author: zhl
* @LastEditTime: 2020-12-22 18:18:19
*/
#include<cstdio>
#include<queue>
#include<map>
#define min(a,b) (a<b?a:b)
#define not !
#define and &&
#define or ||
using namespace std;
int S, N, M;
typedef struct p {
int a, b, c;
p() {}
p(int _a, int _b, int _c) {
a = _a, b = _b, c = _c;
}
bool operator < (const p& rhs)const {
if (a != rhs.a)return a < rhs.a;
if (b != rhs.b)return b < rhs.b;
return c < rhs.c;
}
}tup;
map<tup, int>vis;
bool ok(tup x) {
return (x.a == 0 and x.b == x.c) or (x.b == 0 and x.a == x.c) or (x.c == 0 and x.a == x.b);
}
tup res[6];
void operate(tup x) {
int mx = min(N - x.b, x.a);
res[0] = tup(x.a - mx, x.b + mx, x.c);
mx = min(M - x.c, x.a);
res[1] = tup(x.a - mx, x.b, x.c + mx);
mx = min(S - x.a, x.b);
res[2] = tup(x.a + mx, x.b - mx, x.c);
mx = min(M - x.c, x.b);
res[3] = tup(x.a, x.b - mx, x.c + mx);
mx = min(S - x.a, x.c);
res[4] = tup(x.a + mx, x.b, x.c - mx);
mx = min(N - x.b, x.c);
res[5] = tup(x.a, x.b + mx, x.c - mx);
}
int main() {
while (scanf("%d%d%d", &S, &N, &M) and S != 0) {
queue<tup>Q; Q.push(p(S, 0, 0));
int ans = -1, now = 0;
vis.clear();
while (not Q.empty()) {
int sz = Q.size();
while (sz--) {
tup tp = Q.front(); Q.pop();
if (ok(tp)) {
ans = now;
break;
}
operate(tp);
for (int i = 0; i < 6; i++) {
if (vis.count(res[i]))continue;
Q.push(res[i]);
vis[res[i]] = 1;
}
}
if (ans != -1)break;
now++;
}
if (ans == -1)puts("NO");
else printf("%d
", ans);
}
}
/*
* @Author: zhl
* @LastEditTime: 2020-12-23 10:29:17
*/
#include<cstdio>
#include<cstring>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
#define min(a,b) (a < b ? a : b)
int n, m;
char mp[220][220];
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
struct point {
int x, y;
point() {}
point(int _x, int _y) { x = _x, y = _y; }
bool operator < (const point& b)const {
if (x != b.x)return x < b.x;
return y < b.y;
}
}stA,stB;
int id(point x) {return (x.x - 1) * m + x.y;}
int disA[50000], disB[50000], vis[50000];
void bfs(point st,int* dis) {
memset(vis, 0, sizeof vis); vis[id(st)] = 1;
queue<point>Q;Q.push(st);
int now = 0;
while (not Q.empty()) {
int sz = Q.size();
while (sz--) {
point tp = Q.front(); Q.pop();
dis[id(tp)] = now;
for (int i = 0; i < 4; i++) {
point nxt = point(tp.x + dx[i], tp.y + dy[i]);
if (nxt.x < 1 or nxt.x > n or nxt.y < 1 or nxt.y > m or vis[id(nxt)])continue;
if (mp[nxt.x][nxt.y] == '#')continue;
vis[id(nxt)] = 1;
Q.push(nxt);
}
}
now++;
}
}
int main() {
while (~scanf("%d%d", &n, &m)) {
for (int i = 1; i <= n; i++) {
scanf("%s", mp[i] + 1);
for (int j = 1; j <= m; j++) {
if (mp[i][j] == 'M')stA = point(i, j);
if (mp[i][j] == 'Y')stB = point(i, j);
}
}
memset(disA, 0x3f, sizeof disA); memset(disB, 0x3f, sizeof disB);
bfs(stA, disA); bfs(stB, disB);
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '@') {
ans = min(ans, disA[id(point(i, j))] + disB[id(point(i, j))]);
}
}
}
printf("%d
", ans*11);
}
}
N - Find a way
找一个点到两个点的距离和最小
/*
* @Author: zhl
* @LastEditTime: 2020-12-23 10:29:17
*/
#include<cstdio>
#include<cstring>
#include<queue>
#include<bits/stdc++.h>
using namespace std;
#define min(a,b) (a < b ? a : b)
int n, m;
char mp[220][220];
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
struct point {
int x, y;
point() {}
point(int _x, int _y) { x = _x, y = _y; }
bool operator < (const point& b)const {
if (x != b.x)return x < b.x;
return y < b.y;
}
}stA,stB;
int id(point x) {return (x.x - 1) * m + x.y;}
int disA[50000], disB[50000], vis[50000];
void bfs(point st,int* dis) {
memset(vis, 0, sizeof vis); vis[id(st)] = 1;
queue<point>Q;Q.push(st);
int now = 0;
while (not Q.empty()) {
int sz = Q.size();
while (sz--) {
point tp = Q.front(); Q.pop();
dis[id(tp)] = now;
for (int i = 0; i < 4; i++) {
point nxt = point(tp.x + dx[i], tp.y + dy[i]);
if (nxt.x < 1 or nxt.x > n or nxt.y < 1 or nxt.y > m or vis[id(nxt)])continue;
if (mp[nxt.x][nxt.y] == '#')continue;
vis[id(nxt)] = 1;
Q.push(nxt);
}
}
now++;
}
}
int main() {
while (~scanf("%d%d", &n, &m)) {
for (int i = 1; i <= n; i++) {
scanf("%s", mp[i] + 1);
for (int j = 1; j <= m; j++) {
if (mp[i][j] == 'M')stA = point(i, j);
if (mp[i][j] == 'Y')stB = point(i, j);
}
}
memset(disA, 0x3f, sizeof disA); memset(disB, 0x3f, sizeof disB);
bfs(stA, disA); bfs(stB, disB);
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mp[i][j] == '@') {
ans = min(ans, disA[id(point(i, j))] + disB[id(point(i, j))]);
}
}
}
printf("%d
", ans*11);
}
}