弱菜做了好久23333333........
传送门： http://acm.hust.edu.cn/vjudge/contest/view.action?cid=105278#overview
A 只能摆k个棋子，只能摆在#
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = ;
char maze[max_n][max_n];
bool vis[max_n];
int n, m, ans, cnt;
void init(){
memset(maze, , sizeof(maze));
ans = cnt = ;
}
void dfs(int k){
if(cnt == m){ ++ans; return ; }
if(k > n) return ;
for(int i = ; i < n; ++i){
if(maze[i][k] == '#' && !vis[i]){
vis[i] = ; ++cnt;
dfs(k+);
vis[i] = ; --cnt;
}
}
dfs(k+);
}
int main(){
ios::sync_with_stdio(false);
while(cin >> n >> m){
if(n == m && n == -) break;
init();
for(int i = ; i < n; ++i){
cin.get();
for(int j = ; j < n; ++j) cin >> maze[i][j];
}
dfs();
cout << ans << endl;
}
return ;
}
B 三维BFS
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = ;
const int cx[] = {, , , -, , };
const int cy[] = {, , -, , , };
const int cz[] = {, , , , , -};
int maze[max_n][max_n][max_n];
bool vis[max_n][max_n][max_n];
struct point{
int x, y, z, step;
};
int L, R, C;
int ex, ey, ez;
int main(){
ios::sync_with_stdio(false);
while(cin >> L >> R >> C){
if(L == && R == && C == ) break;
queue<point> q;
memset(vis, , sizeof(vis));
memset(maze, , sizeof(maze));
for(int k = ; k < L; ++k){
for(int i = ; i < R; ++i){
cin.get();
for(int j = ; j < C; ++j){
char ch = cin.get();
if(ch == 'S'){
maze[k][i][j] = ;
point p = {k, i, j, };
q.push(p);
}
else if(ch == '.') maze[k][i][j] = ;
else if(ch == 'E'){
maze[k][i][j] = ;
ex = k; ey = i; ez = j;
}
}
}
cin.get();
}
int x, y, z, step;
while(!q.empty()){
point p = q.front();
q.pop();
x = p.x, y = p.y, z = p.z, step = p.step;
if(x == ex && y == ey && z == ez) break;
for(int i = ; i < ; ++i){
int nx = x + cx[i], ny = y + cy[i], nz = z + cz[i];
if(nx<||L<nx||ny<||R<ny||nz<||C<nz) continue;
if(maze[nx][ny][nz]){
maze[nx][ny][nz] = ;
point tp = {nx, ny, nz, step + };
q.push(tp);
}
}
}
if(x == ex && y == ey && z == ez) printf("Escaped in %d minute(s).\n", step);
else printf("Trapped!\n");
}
return ;
}
C 搜......
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct point{
int x, step;
};
int S, E;
int vis[];
int main(){
ios::sync_with_stdio(false);
while(cin >> S >> E){
memset(vis, , sizeof(vis));
vis[S] = ;
queue<point> q;
q.push(point{S, });
int x, step;
while(!q.empty()){
point p = q.front();
x = p.x; step = p.step;
q.pop();
if(x == E) break;
for(int i = ; i < ; ++i){
int nx;
if(i == ) nx = x + ;
else if(i == ) nx = x - ;
else nx = x << ;
if( <= nx && nx <= && !vis[nx]){ q.push(point{nx, step+}); vis[nx] = ; }
}
}
cout << step << endl;
}
return ;
}
D 卡了好久看了题解 第一行确定下来后其他行的也都确定下来了(说的好有道理)，所以枚举第一行状态，确定下其他行，看最后一行是否都是0
然后在这道题发现了之前二进制枚举的一个错误....... 正确姿势：(i>>j) & 1（吧？）
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int MAXN = ;
const int INF = 0x3f3f3f3f;
const int cx[] = {, , -, };
const int cy[] = {, -, , };
int n, m;
int ans[MAXN][MAXN];
int flip[MAXN][MAXN];
int origin[MAXN][MAXN]; int check(int x, int y){
int cnt = origin[x][y];
for(int i = ; i < ; ++i){
int nx = x + cx[i], ny = y + cy[i];
if(nx >= && nx < n && ny >= && ny < m)
cnt += flip[nx][ny];
}
return cnt & ;
} int duang(){
for(int i = ; i < n; ++i)
for(int j = ; j < m; ++j)
if(check(i-, j)) flip[i][j] = ;
for(int j = ; j < m; ++j)
if(check(n-, j)) return ;
int cnt = ;
for(int i = ; i < n; ++i)
for(int j = ; j < m; ++j)
cnt += flip[i][j];
return cnt;
} int main(){
while(cin >> n >> m){
memset(origin, , sizeof(origin));
for(int i = ; i < n; ++i)
for(int j = ; j < m; ++j)
cin >> origin[i][j];
int tans = INF;
for(int i = ; i < (<<m); ++i){
memset(flip, , sizeof(flip));
for(int j = ; j < m; ++j)
flip[][j] = (i>>j) & ;
int cnt = duang();
if(cnt < tans && cnt != ){
tans = cnt;
memcpy(ans, flip, sizeof(flip));
}
}
if(tans == INF) cout << "IMPOSSIBLE" << endl;
else{
for(int i = ; i < n; ++i)
for(int j = ; j < m; ++j)
cout << ans[i][j] << " \n"[j==m-];
}
}
return ;
}
E 听说答案都在long long范围内hhhh.......
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
int n;
while(cin >> n){
if(n == ) break;
queue<ll> q;
q.push(1LL);
while(!q.empty()){
ll k = q.front();
q.pop();
if(k % n == ){
cout << k << endl;
break;
}
q.push(k*);
q.push(k*+);
}
}
return ;
}
F GOJ有这道题........
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
int m, n;
bool isPrime[];
int vis[];
void preprocess(){
memset(isPrime, true, sizeof(isPrime));
isPrime[] = isPrime[] = false;
for(int i = ; i < ; ++i){
if(isPrime[i]){
for(int j = i; i*j < ; ++j){
isPrime[i*j] = false;
}
}
}
}
void bfs(){
memset(vis, , sizeof(vis));
vis[m] = ;
queue<int> q;
q.push(m);
while(!q.empty()){
int k = q.front();
q.pop();
int d[] = {k/, k%/, k%/, k%};
int b[] = {, , , };
for(int i = ; i < ; ++i){
for(int j = ; j < ; ++j){
int t = k - d[i] * b[i] + j * b[i];
if(k == n) return ;
if(t > && isPrime[t] && !vis[t]){
vis[t] = vis[k] + ;
q.push(t);
}
}
}
}
return ;
}
int main(){
ios::sync_with_stdio(false);
preprocess();
int t;
cin >> t;
while(t--){
cin >> m >> n;
bfs();
if(vis[n]) cout << vis[n]- << endl;
else cout << "Impossible" << endl;
}
return ;
}
G 水 直接模拟 略坑是第一张都是最底的一张
#include <set>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std; int main(){
int t;
cin >> t;
for(int x = ; x <= t; ++x){
int l;
cin >> l;
string str1, str2, desstr;
cin >> str1 >> str2 >> desstr;
int step = ;
set<string> s;
s.insert(str1+str2);
bool flag = true;
while(flag){
string tmpstr;
for(int i = ; i < l; ++i){
tmpstr += str2[i];
tmpstr += str1[i];
}
//cout << tmpstr << endl;
++step;
if(tmpstr == desstr) break;
if(s.count(tmpstr)){
flag = false;
break;
}
s.insert(tmpstr);
str1 = tmpstr.substr(, l);
str2 = tmpstr.substr(l, *l);
//cout << str1 << " " << str2 << endl;
}
cout << x << ' ' << (flag ? step : -) << endl;
}
return ;
}
H M题写吐了H不想做.......
还是搜 6种状态
I 暴力找两个#搜.......
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int INF = 0x3f3f3f;
const int cx[] = {, , , -};
const int cy[] = {, -, , };
int n, m;
int dis[][];
char map[][]; struct Point{
int x, y;
Point(){}
Point(int xx, int yy) :x(xx), y(yy){}
};
queue<Point> q;
int bfs(int x1, int y1, int x2, int y2){
memset(dis, INF, sizeof(dis));
q.push(Point(x1, y1));
q.push(Point(x2, y2));
dis[x1][y1] = ;
dis[x2][y2] = ;
while (!q.empty()){
Point p = q.front();
q.pop();
for (int i = ; i < ; i++){
int xx = p.x + cx[i], yy = p.y + cy[i];
if (xx >= && xx < n && yy >= && yy<m && map[xx][yy] == '#' && dis[xx][yy] > dis[p.x][p.y] + ){
dis[xx][yy] = dis[p.x][p.y] + ;
q.push(Point(xx, yy));
}
}
} int ret = ;
for (int i = ; i < n; i++)
for (int j = ; j < m; j++)
if (map[i][j] == '#')
ret = max(ret, dis[i][j]);
return ret;
} int main(){
int t;
cin >> t;
for (int x = ; x <= t; x++){
while(!q.empty()) q.pop();
cin >> n >> m;
for (int i = ; i < n; i++)
cin >> map[i];
int ans = INF;
for (int i = ; i < n; i++)
for (int j = ; j < m; j++)
if (map[i][j] == '#')
for (int ii = ; ii < n; ii++)
for (int jj = ; jj < m; jj++)
if (map[ii][jj] == '#'){
int temp = bfs(i, j, ii, jj);
ans = min(ans, temp);
}
if (ans == INF) ans = -;
cout << "Case " << x << ": " << ans << endl;
}
return ;
}
J 多处火.....先处理火，再处理人，遇到可行的情况退出来
#include <bits/stdc++.h>
using namespace std; struct pos{
int x, y;
pos(int xx = , int yy = ): x(xx), y(yy) {}
};
const int MAXN = ;
const int INF = 0x7f7f7f7f;
const int cx[] = {, , , -};
const int cy[] = {, -, , };
int n, m;
int jx, jy, fx, fy;
int maze[MAXN][MAXN];
int jstep[MAXN][MAXN];
int fstep[MAXN][MAXN]; int main(){
int t;
cin >> t;
while(t--){
cin >> n >> m;
queue<pos> qf;
memset(fstep, -, sizeof(fstep));
for(int i = ; i < n; ++i){
cin.get();
for(int j = ; j < m; ++j){
char ch;
cin >> ch;
if(ch == '#') maze[i][j] = ;
else{
maze[i][j] = ;
if(ch == 'J'){
jx = i;
jy = j;
}
else if(ch == 'F'){
fx = i;
fy = j;
qf.push(pos(fx, fy));
fstep[fx][fy] = ;
}
}
}
}
while(!qf.empty()){
pos p = qf.front();
int x = p.x, y = p.y;
qf.pop();
for(int i = ; i < ; ++i){
int nx = x + cx[i], ny = y + cy[i];
if(nx < || n <= nx || ny < || m <= ny || maze[nx][ny] == || fstep[nx][ny] != -) continue;
qf.push(pos(nx, ny));
fstep[nx][ny] = fstep[x][y] + ;
}
}
// cout << endl;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j)
// cout << fstep[i][j] << '\t';
// cout << endl;
// }
memset(jstep, -, sizeof(jstep));
queue<pos> qj;
qj.push(pos(jx, jy));
jstep[jx][jy] = ;
int ans = -;
while(!qj.empty()){
pos p = qj.front();
int x = p.x, y = p.y;
qj.pop();
if(x == || x == n- || y == || y == m-){
ans = jstep[x][y];
break;
}
for(int i = ; i < ; ++i){
int nx = x + cx[i], ny = y + cy[i];
if(nx < || n <= nx || ny < || m <= ny || maze[nx][ny] == || jstep[nx][ny] != - || (fstep[nx][ny] != - && fstep[nx][ny] <= jstep[x][y] + )) continue;
qj.push(pos(nx, ny));
jstep[nx][ny] = jstep[x][y] + ;
}
}
// cout << endl;
// for(int i = 0; i < n; ++i){
// for(int j = 0; j < m; ++j)
// cout << jstep[i][j] << '\t';
// cout << endl;
// }
if(ans == -) cout << "IMPOSSIBLE" << endl;
else cout << ans+ << endl;
}
return ;
}
K 搜 开数组记录上一个点的坐标
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
struct point{
int x, y;
};
int maze[][];
point state[][];
const int cx[] = {, , , -};
const int cy[] = {, -, , };
int main(){
ios::sync_with_stdio(false);
memset(state, , sizeof(state));
for(int i = ; i < ; ++i)
for(int j = ; j < ; ++j)
cin >> maze[i][j];
queue<point> q;
q.push({, });
maze[][] = ;
bool flag = false;
while(!q.empty()){
point k = q.front();
q.pop();
for(int i = ; i < ; ++i){
int x = k.x + cx[i], y = k.y + cy[i];
if(x < || x > || y < || y > || maze[x][y]) continue;
q.push({x, y});
maze[x][y] = ;
state[x][y] = k;
if(x == && y == ){
flag = true;
break;
}
}
if(flag) break;
}
point k = {, };
stack<point> s;
while(!(k.x == && k.y == )){
s.push(k);
k = state[k.x][k.y];
}
s.push(point{, });
while(!s.empty()){
cout << "(" << s.top().x << ", " << s.top().y << ")" << endl;
s.pop();
}
return ;
}
L 数水坑类的 8个方向
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int ans;
char maze[][];
const int cx[] = {, , , , , -, -, -};
const int cy[] = {, -, , -, , , , -};
void dfs(int x, int y){
maze[x][y] = '*';
for(int i = ; i < ; ++i){
int nx = x + cx[i], ny = y + cy[i];
if(maze[nx][ny] == '@') dfs(nx, ny);
}
}
int main(){
ios::sync_with_stdio(false);
int m, n;
while(cin >> m >> n){
if(m == && n == ) break;
ans = ;
for(int i = ; i < m; ++i){
cin.get();
for(int j = ; j < n; ++j)
cin >> maze[i][j];
}
for(int i = ; i < m; ++i){
for(int j = ; j < n; ++j){
if(maze[i][j] == '@'){
++ans;
dfs(i, j);
}
}
}
cout << ans << endl;
}
return ;
}
M 可乐.....改了好久蜜汁哇 果断重写 简直恶心
#include <bits/stdc++.h>
using namespace std;
//#define print() cout<<ts<<" "<<tn<<" "<<tm<<endl; struct state{
int s, n, m;
state(int ss = , int nn = , int mm = ): s(ss), n(nn), m(mm) {}
};
int s, n, m;
queue<state> q;
const int MAXN = ;
int step[MAXN][MAXN][MAXN]; int main(){
while(cin >> s >> n >> m){
if(s == && n == && m == ) break;
if(s & ) cout << "NO" << endl;
else{
while(!q.empty()) q.pop();
memset(step, -, sizeof(step));
int ans = -;
q.push(state(s, , ));
step[s][][] = ;
while(!q.empty()){
state p = q.front();
q.pop();
int ss = p.s, nn = p.n, mm = p.m;
if((ss == s/ && nn == s/) || (ss == s/ && mm == s/) || (nn == s/ && mm == s/)){
ans = step[ss][nn][mm];
break;
}
state tmp;
//s -> n || s -> m
if(ss){
//s -> n
if(ss > n - nn){
tmp.s = ss - (n - nn);
tmp.n = n;
tmp.m = mm;
}
else{
tmp.s = ;
tmp.n = nn + ss;
tmp.m = mm;
}
if(step[tmp.s][tmp.n][tmp.m] == -){
step[tmp.s][tmp.n][tmp.m] = step[ss][nn][mm] + ;
q.push(tmp);
}
//ss -> m
if(ss > m - mm){
tmp.s = ss - (m - mm);
tmp.m = m;
tmp.n = nn;
}
else{
tmp.s = ;
tmp.m = mm + ss;
tmp.n = nn;
}
if(step[tmp.s][tmp.n][tmp.m] == -){
step[tmp.s][tmp.n][tmp.m] = step[ss][nn][mm] + ;
q.push(tmp);
}
}
//n -> s || n -> m
if(nn){
//n -> s
if(nn > s - ss){
tmp.n = nn - (s - ss);
tmp.s = s;
tmp.m = mm;
}
else{
tmp.n = ;
tmp.s = ss + nn;
tmp.m = mm;
}
if(step[tmp.s][tmp.n][tmp.m] == -){
step[tmp.s][tmp.n][tmp.m] = step[ss][nn][mm] + ;
q.push(tmp);
}
//n -> m
if(nn > m - mm){
tmp.n = nn - (m - mm);
tmp.m = m;
tmp.s = ss;
}
else{
tmp.n = ;
tmp.m = mm + nn;
tmp.s = ss;
}
if(step[tmp.s][tmp.n][tmp.m] == -){
step[tmp.s][tmp.n][tmp.m] = step[ss][nn][mm] + ;
q.push(tmp);
}
}
//m -> n || m -> s
if(mm){
//m -> n
if(mm > n - nn){
tmp.m = mm - (n - nn);
tmp.n = n;
tmp.s = ss;
}
else{
tmp.m = ;
tmp.n = nn + mm;
tmp.s = ss;
}
if(step[tmp.s][tmp.n][tmp.m] == -){
step[tmp.s][tmp.n][tmp.m] = step[ss][nn][mm] + ;
q.push(tmp);
}
//m -> s
if(mm > s - ss){
tmp.m = mm - (s - ss);
tmp.s = s;
tmp.n = nn;
}
else{
tmp.m = ;
tmp.s = mm + ss;
tmp.n = nn;
}
if(step[tmp.s][tmp.n][tmp.m] == -){
step[tmp.s][tmp.n][tmp.m] = step[ss][nn][mm] + ;
q.push(tmp);
}
}
}
if(ans == -) cout << "NO" << endl;
else cout << ans << endl;
}
}
return ;
}
N 从两个人的位置开始bfs整个图
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; struct pos{
int x, y;
pos(int xx, int yy): x(xx), y(yy){};
};
const int MAXN = ;
char maze[MAXN][MAXN];
const int cx[] = {, -, , };
const int cy[] = {, , , -};
vector<pos> kfc;
queue<pos> qy; int yx, yy, stepy[MAXN][MAXN];
queue<pos> qm; int mx, my, stepm[MAXN][MAXN]; int main(){
int n, m;
while(cin >> n >> m){
kfc.clear();
for(int i = ; i < n; ++i){
cin.get();
for(int j = ; j < m; ++j){
char ch;
cin >> ch;
if(ch == '#') maze[i][j] = ch;
else{
if(ch == 'Y'){
yx = i;
yy = j;
}
if(ch == 'M'){
mx = i;
my = j;
}
if(ch == '@')
kfc.push_back(pos(i, j));
maze[i][j] = '.';
}
}
}
while(!qy.empty()) qy.pop();
while(!qm.empty()) qm.pop();
memset(stepy, -, sizeof(stepy));
memset(stepm, -, sizeof(stepm));
qy.push(pos(yx, yy));
stepy[yx][yy] = ;
while(!qy.empty()){
int x = qy.front().x, y = qy.front().y;
qy.pop();
for(int i = ; i < ; ++i){
int nx = x + cx[i], ny = y + cy[i];
if(nx < || n < nx || ny < || m < ny || maze[nx][ny] == '#' || stepy[nx][ny] != -) continue;
stepy[nx][ny] = stepy[x][y] + ;
qy.push(pos(nx, ny));
}
}
qm.push(pos(mx, my));
stepm[mx][my] = ;
while(!qm.empty()){
int x = qm.front().x, y = qm.front().y;
qm.pop();
for(int i = ; i < ; ++i){
int nx = x + cx[i], ny = y + cy[i];
if(nx < || n < nx || ny < || m < ny || maze[nx][ny] == '#' || stepm[nx][ny] != -) continue;
stepm[nx][ny] = stepm[x][y] + ;
qm.push(pos(nx, ny));
}
}
int ans = 0x7f7f7f7f;
for(vector<pos>::iterator i = kfc.begin(); i != kfc.end(); ++i){
int x = (*i).x, y = (*i).y;
ans = min(ans, stepy[x][y] + stepm[x][y]);
}
cout << ans* << endl;
}
return ;
}
.............................................................................