简单搜索
///没想到保存草稿成功还能一夜回到解放前，写好的解释都没了，就看看代码ba
棋盘问题
dfs一行(hang)一行搜索可能解，任意行可能放或不放，用visy[]记录此列是否放过棋子
ac代码
#include<bits/stdc++.h>
using namespace std;
char qi[9][9];
int n,k,ans;
bool visy[9];
void dfs(int x,int s){
if(s==k){
ans+=1;
return;
}
if(x>n) return;
for(int j=1;j<=n;j++){
if(qi[x][j]=='#'&&!visy[j]){
visy[j]=1;
dfs(x+1,s+1); //第x行放棋子
visy[j]=0;
}
}
dfs(x+1,s); //第x行不放棋子
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
while(cin>>n>>k&&n!=-1){
ans=0;
memset(visy,0,sizeof(visy));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>qi[i][j];
}
}
dfs(1,0);
printf("%d\n",ans);
}
return 0;
}
Dungeon Master
AC代码
#incldue<bits/stdc++.h>
using namespace std;
#define ll int
char p[35][35][35];
ll L, R, C;
bool vis[35][35][35];
ll direct[6][3] = { {0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0} };
typedef struct {
ll x, y, z, s;
}pi;
pi S;
pi newp;
ll bfs(pi S) {
queue <pi> q;
q.push(S);
while (!q.empty()) {
pi temp = q.front();
q.pop();
for (ll i = 0;i < 6;i++) {
newp.x = temp.x + direct[i][0];
newp.y = temp.y + direct[i][1];
newp.z = temp.z + direct[i][2];
newp.s = temp.s + 1;
if (1 <= newp.x && newp.x <= L && 1 <= newp.y && newp.y <= R && 1 <= newp.z && newp.z <= C && !vis[newp.x][newp.y][newp.z] && p[newp.x][newp.y][newp.z] != '#') {
vis[newp.x][newp.y][newp.z] = 1;
if (p[newp.x][newp.y][newp.z] == 'E') return newp.s;
q.push(newp);
}
}
}
return 0;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
while (cin >> L >> R >> C && L) {
memset(vis, 0, sizeof(vis));
for (ll i = 1;i <= L;i++) {
for (ll j = 1;j <= R;j++) {
for (ll k = 1;k <= C;k++) {
cin >> p[i][j][k];
if (p[i][j][k] == 'S') {
S.x = i;
S.y = j;
S.z = k;
S.s = 0;
}
}
}
}
ll step = bfs(S);
if (step) {
cout << "Escaped in " << step << " minute(s)." << endl;
}
else {
cout << "Trapped!" << endl;
}
}
return 0;
}
Catch That Cow
ac代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, k, vis[100005];
typedef struct {
ll x;
ll step;
}bu;
bu S,newt;
ll bfs(bu a) {
queue <bu> q;
q.push(a);
while (!q.empty()) {
bu temp = q.front();
q.pop();
if (temp.x == k) return temp.step;
if (temp.x + 1 <= 100000 && !vis[temp.x + 1]) {
vis[temp.x + 1] = 1;
newt.x = temp.x + 1;
newt.step = temp.step + 1;
q.push(newt);
}
if (temp.x - 1 >= 0 && temp.x - 1 <= 100000 && !vis[temp.x - 1]) {
vis[temp.x - 1] = 1;
newt.x = temp.x - 1;
newt.step = temp.step + 1;
q.push(newt);
}
if (2 * temp.x <= 100000 && !vis[2 * temp.x]) {
vis[2 * temp.x] = 1;
newt.x = 2 * temp.x;
newt.step = temp.step + 1;
q.push(newt);
}
}
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> S.x >> k;
S.step = 0;
if (S.x == k) cout << 0 << endl;
else cout << bfs(S) << endl;
return 0;
}
Fliptile
AC代码
#include<bits/stdc++.h>
using namespace std;
#define maxn 20
//放置原布置，新布置方法，答案布置方法
int a[maxn][maxn], newa[maxn][maxn], ansa[maxn][maxn];
int n, m;
//会改变它颜色的几个翻法
int dir[5][2] = { {0,0},{1,0},{-1,0},{0,1},{0,-1} };
//获取目前(x,y)的颜色
int get(int x, int y) {
int col = a[x][y];
int newx, newy;
for (int i = 0;i < 5;i++) {
newx = x + dir[i][0];
newy = y + dir[i][1];
col += newa[newx][newy];
}
return col % 2;
}
int fan() {
int res = 0;
for (int i = 1;i < n;i++) {
for (int j = 0;j < m;j++) {
if (get(i - 1, j)) newa[i][j] = 1;
}
}
for (int j = 0;j < m;j++) {
if (get(n - 1, j)) return -1;
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
res += newa[i][j];
}
}
return res;
}
void solve() {
int res = -1;
for (int i = 0;i < 1 << m;i++) {
memset(newa, 0, sizeof(newa));
for (int j = 0;j < m;j++) {
newa[0][j] = i >> j & 1;
}
int ans = fan();
if (ans >= 0 && (res<0 || res>ans)) {
res = ans;
memcpy(ansa, newa, sizeof(newa));
}
}
if (res < 0) cout << "IMPOSSIBLE" << endl;
else
{
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
cout << ansa[i][j] << " ";
}
cout << endl;
}
}
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> m;
for (int i = 0;i < n;i++) {
for (int j = 0;j < m;j++) {
cin >> a[i][j];
}
}
solve();
return 0;
}
Find The Multiple
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
ll n;
void bfs() {
queue <ll> q;
q.push(1);
while (1) {
ll temp = q.front();
if (temp % n == 0) {
cout << temp << endl;
return;
}
q.pop();
for (ll i = 0;i <= 1;i++) q.push(10 * temp + i);
}
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
while (cin >> n && n) bfs();
return 0;
}
Prime Path
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
ll t, n, m, ans, vis[10000], book[10000];
ll c[4] = { 1000,100,10,1 };
vector <ll> p;
typedef struct {
ll x, step;
}su;
su S, newS;
void getp() {
for (ll i = 2;i <= 10000;i++) {
if (vis[i]) continue;
vis[i] = 1;
book[i] = 1;
for (ll j = i;j <= 10000 / i;j++) vis[i * j] = 1;
}
}
ll bfs() {
queue <su> q;
q.push(S);
vis[S.x] = 1;
while (!q.empty()) {
su temp = q.front();
if (temp.x == m) return temp.step;
q.pop();
for (ll i = 0;i < 4;i++) {
for (ll j = 0;j <= 9;j++) {
if (!i && !j) continue;
newS.x = temp.x - temp.x / c[i] % 10 * c[i] + j * c[i];
newS.step = temp.step + 1;
if (!vis[newS.x] && book[newS.x] && newS.x <= 9999 && newS.x >= 1000) {
vis[newS.x] = 1;
q.push(newS);
}
}
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> t;
getp();
while (t--) {
memset(vis, 0, sizeof(vis));
cin >> S.x >> m;
S.step = 0;
ans = bfs();
if (ans < 0) cout << "Impossible" << endl;
else cout << ans << endl;
}
return 0;
}
Shuffle’m Up
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
ll t, n, step=0, ii;
string S1, S2, S12, temp;
void solve() {
map<string, ll> vis;
temp = S1 + S2;
step = 0;
while (temp != S12) {
vis[temp] = 1;
string newt = "";
for (ll i = 0;i < n;i++) {
newt += temp[i+n];
newt += temp[i];
}
step++;
temp = newt;
if (vis[temp]) {
cout << ii <<" "<< -1 << endl;
return;
}
}
cout << ii <<" "<< step << endl;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> t;
for(ii=1;ii<=t;ii++) {
cin >> n >> S1 >> S2 >> S12;
solve();
}
return 0;
}
Pots
记忆化广搜
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
ll a, b, c, book[105][105], op, tx, ty, head, tail, flag=0;
string print[6] = { "FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)" };
typedef struct {
ll x, y, step, f, ope;
}pot;
pot q[1005];
void dfs(pot now) {
if (now.f == -1) return;
dfs(q[now.f]);
cout << print[now.ope] << endl;
}
void pan() {
if (!book[tx][ty]) {
book[tx][ty] = 1;
q[tail].x = tx;
q[tail].y = ty;
q[tail].step = q[head].step + 1;
q[tail].f = head;
q[tail].ope = op;
tail++;
}
if (tx == c || ty == c) flag = 1;
}
void fill(ll tt) {
if (tt) {
tx = q[head].x;
ty = b;
op = 1;
}
else{
tx = a;
ty = q[head].y;
op = 0;
}
pan();
}
void drop(ll tt) {
if (tt) {
tx = q[head].x;
ty = 0;
op = 3;
}
else {
tx = 0;
ty = q[head].y;
op = 2;
}
pan();
}
void pour(ll tt) {
if (tt) {
tx = q[head].x + q[head].y <= a ? q[head].x + q[head].y : a;
ty = tx == a ? q[head].x + q[head].y - a : 0;
op = 5;
}
else {
ty = q[head].x + q[head].y <= b ? q[head].x + q[head].y : b;
tx = ty == b ? q[head].x + q[head].y - b : 0;
op = 4;
}
pan();
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> a >> b >> c;
head = 1; tail = 1;
q[head].x = 0;
q[head].y = 0;
q[head].step = 0;
q[head].f = -1;
tail++;
book[0][0] = 1;
while (head < tail) {
for (ll i = 0;i < 2;i++) {
fill(i);
if (flag) break;
drop(i);
if (flag) break;
pour(i);
if (flag) break;
}
if (flag) break;
head++;
}
if (flag) {
cout << q[tail - 1].step << endl;
dfs(q[tail - 1]);
}
else cout << "impossible" << endl;
return 0;
}
Fire Game
双起点BFS
用pair<>记录点坐标
用d[x][y]记录至x,y所需时间
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define inf 1000000
ll n, m, t, ans, dx, dy, num=0, ana;
char grass[105][105];
typedef pair <ll, ll> P;
P fire[105], S, temp;
ll dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
ll d[105][105], vis[105][105];
ll bfs(P x,P y) {
queue <P> q;
memset(vis, 0, sizeof(vis));
memset(d, -1, sizeof(d));
q.push(x), q.push(y);
d[x.first][x.second] = 0, d[y.first][y.second] = 0;
vis[x.first][x.second] = 1, vis[y.first][y.second] = 1;
while(!q.empty()) {
temp = q.front();
q.pop();
for (ll i = 0;i < 4;i++) {
dx = temp.first + dir[i][0], dy = temp.second + dir[i][1];
if (dx<0||dx>=n||dy<0||dy>=m||vis[dx][dy]||grass[dx][dy]!='#') continue;
vis[dx][dy] = 1;
d[dx][dy] = d[temp.first][temp.second] + 1;
q.push(P(dx, dy));
}
}
for (ll i = 0;i < num;i++) {
if (d[fire[i].first][fire[i].second] == -1) return -1;
}
return d[temp.first][temp.second];
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> t;
for(ll tt=1;tt<=t;tt++) {
num = 0;
ans = inf;
cin >> n >> m;
memset(fire, 0, sizeof(fire));
for (ll i = 0;i < n;i++) {
for (ll j = 0;j < m;j++) {
cin >> grass[i][j];
if (grass[i][j] == '#') fire[num].first = i, fire[num++].second = j;
}
}
if (num <= 1) {
cout << "Case " << tt << ": " << 0 << endl;
continue;
}
for (ll i = 0;i < num;i++) {
for (ll j = i + 1;j < num;j++) {
ana = bfs(fire[i], fire[j]);
if (ana == -1) continue;
ans = min(ans, ana);
}
}
if (ans != inf) cout << "Case " << tt << ": " << ans << endl;
else cout << "Case " << tt << ": " << -1 << endl;
}
return 0;
}
Oil Deposits
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
ll n, m, cnt, num, vis[105][105];
ll dir[8][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1} };
char place[105][105];
typedef pair <ll, ll> P;
P newt;
void bfs(P S) {
queue <P> q;
q.push(S);
vis[S.first][S.second] = 1;
while (q.size()) {
P temp = q.front();
q.pop();
for (ll i = 0;i < 8;i++) {
newt.first = temp.first + dir[i][0];
newt.second = temp.second + dir[i][1];
if (newt.first >= 0 && newt.first < n && newt.second >= 0 && newt.second < m && !vis[newt.first][newt.second]&&place[newt.first][newt.second]=='@') {
vis[newt.first][newt.second] = 1;
q.push(newt);
}
}
}
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
while (cin >> n >> m && n) {
num = 0, cnt=0;
P white[10006];
memset(vis, 0, sizeof(vis));
for (ll i = 0;i < n;i++) {
for (ll j = 0;j < m;j++) {
cin >> place[i][j];
if (place[i][j] == '@') white[++num]=make_pair(i, j);
}
}
for (ll i = 1;i <= num;i++) {
if (!vis[white[i].first][white[i].second]) cnt++,bfs(white[i]);
}
cout << cnt << endl;
}
return 0;
}
非常可乐
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
ll a, b, c;
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
while (cin >> a >> b >> c && a) {
a /= gcd(b, c);
if (a & 1) cout << "NO" << endl;
else cout << a - 1 << endl;
}
return 0;
}
Find a way
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
ll n, m, vis[300][300], time1[300][300], time2[300][300];
ll dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
typedef struct {
ll x, y, s;
}peo;
peo Y, M, temp, newt;
char place[300][300];
void bfs(peo S,ll num) {
queue <peo> q;
memset(vis, 0, sizeof(vis));
q.push(S);
vis[S.x][S.y] = 1;
while (q.size()) {
temp = q.front();
q.pop();
if (place[temp.x][temp.y] == '@') {
if (num == 1) time1[temp.x][temp.y] = temp.s;
else if(num==2) time2[temp.x][temp.y] = temp.s;
}
for (ll i = 0;i < 4;i++) {
newt.x = temp.x + dir[i][0];
newt.y = temp.y + dir[i][1];
newt.s = temp.s + 1;
if (newt.x>=0 && newt.x<n && newt.y>=0 && newt.y<m && place[newt.x][newt.y] != '#' && !vis[newt.x][newt.y]) {
vis[newt.x][newt.y] = 1;
q.push(newt);
}
}
}
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
while (cin >> n >> m) {
ll res = 1000000;
for (ll i = 0;i < n;i++) {
for (ll j = 0;j < m;j++) {
cin >> place[i][j];
if (place[i][j] == 'Y') Y.x = i, Y.y = j, Y.s = 0;
else if (place[i][j] == 'M') M.x = i, M.y = j, M.s = 0;
}
}
memset(time1, -1, sizeof(time1));
memset(time2, -1, sizeof(time2));
bfs(Y, 1);
bfs(M, 2);
for (ll i = 0;i < n;i++) {
for (ll j = 0;j < m;j++) {
if (place[i][j] == '@' && time1[i][j] != -1 && time2[i][j] != -1) res = min(res, time1[i][j] + time2[i][j]);
}
}
cout << res * 11 << endl;
}
return 0;
}
版权声明：本文为chabeizip原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。