A
int n, k;
char s[10][10];
ll ans;
int d[4][2] = { -1,0,1,0,0,-1,0,1 };
int w[15];
void dfs(int x,int y)
{
if (y > k)
{
ans++;
return;
}
for (int i = x; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (s[i][j] == '#' && w[j] == 0)
{
w[j] = 1;
dfs(i + 1, y + 1);
w[j] = 0;
}
}
}
}
int main()
{
while (cin >> n >> k && (k != -1 && n != -1))
{
memset(w, 0, sizeof(w));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> s[i][j];
ans = 0;
dfs(1, 1);
cout << ans << endl;
}
return 0;
}
B - Perket
int n;
int a[15],b[15];
int c = 1, q = 0;
int ans = 1e9, f[12];
void dfs(int x)
{
if (x > n)return;
else
{
for (int i = 0; i < n; i++)
{
if (f[i] == 0)
{
c *= a[i];
q += b[i];
f[i] = 1;
ans = min(ans, abs(c - q));
dfs(x + 1);
f[i] = 0;
c /= a[i];
q -= b[i];
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
dfs(1);
cout << ans;
return 0;
}
C - 全排列
int main()
{
char s[10];
scanf("%s", s);
int len = strlen(s);
do
{
for (int i = 0; i < len; i++)
printf("%c", s[i]);
puts("");
} while (next_permutation(s, s + len));
return 0;
}
D - 自然数拆分
int n;
int a[1000] = { 1 };
void pr(int t)
{
printf("%d=", n);
for (int i = 1; i <= t - 1; i++)
printf("%d+", a[i]);
printf("%dn", a[t]);
}
void solve(int x, int t)
{
for (int i = a[t - 1]; i <= x; i++)
{
if (i < n)
{
a[t] = i;
x -= i;
if (x == 0)
pr(t);
else
solve(x, t + 1);
x += i;
}
}
}
int main()
{
scanf("%d", &n);
solve(n, 1);
return 0;
}
E - Prime Ring Problem
int n;
int prime[40];
int ans[20];
int w[20];
void p()
{
for (int i = 2; i <= 40; i++)
{
int flag = 1;
for(int j=2;j<=sqrt(i);j++)
if (i % j == 0)
{
flag = 0;
break;
}
if (flag)prime[i] = 1;
else prime[i] = 0;
}
}
void dfs(int step)
{
if (step > n&&prime[ans[n]+ans[1]])
{
for (int i = 1; i < n; i++)
cout << ans[i] << " ";
cout << ans[n];
cout << endl;
return;
}
for (int i = 2; i <= n; i++)
{
ans[step] = i;
if (w[i] == 1)continue;
else if (prime[ans[step] + ans[step - 1]] == 0)
continue;
w[i] = 1;
dfs(step + 1);
w[i] = 0;
}
}
int main()
{
p();
int i = 0;
while (cin >> n)
{
i++;
if (i >= 2)
cout << endl;
memset(ans, 0, sizeof(ans));
memset(w, 0, sizeof(w));
printf("Case %d:n", i);
w[1] = 1; ans[1] = 1;
dfs(2);
}
return 0;
}
F - Red and Black
int n, m;
char s[25][25];
int res;
int d[4][2] = { 0,1,0,-1,1,0,-1,0 };
int a, b;
bool rode[25][25];
void dfs(int x, int y)
{
for (int i = 0; i < 4; i++)
{
int xx = x + d[i][0], yy = y + d[i][1];
if (s[xx][yy]=='#'||xx<1 || xx>m || yy<1 || yy>n || rode[xx][yy])
continue;
rode[xx][yy] = true;
res++;
dfs(xx, yy);
}
}
int main()
{
while (cin >> n >> m)
{
memset(rode, false, sizeof(rode));
if (n == 0 && m == 0)
break;
for (int i = 1; i <= m; i++)
for (int j = 1; j <=n; j++)
{
cin >> s[i][j];
if (s[i][j] == '@')
{
a = i;
b = j;
}
}
res = 1;
rode[a][b] = 1;
dfs(a, b);
cout << res << endl;
}
return 0;
}
G - Knight Moves
int d[8][2] = {
{-1,-2},{-2,-1},{-2,1},{-1,2},{1,-2},{2,-1},{2,1}, {1,2}
};
int n, x, y, p, q, l;
int ans[305][305];
int main()
{
cin >> n;
while (n--)
{
memset(ans, -1, sizeof(ans));
cin >> l >> x >> y >> p >> q;
ans[x][y] = 0;
queue< pair >bf;
bf = queue< pair >();
bf.push({ x,y });
while (!bf.empty())
{
pair w;
w = bf.front(); bf.pop();
int xx = w.first, yy = w.second;
if (xx == p && yy == q)
break;
int res = ans[xx][yy];
for (int i = 0; i < 8; i++)
{
int nowx = xx + d[i][0], nowy = yy + d[i][1];
if (ans[nowx][nowy]!=-1 ||nowx < 0 || nowx >= l || nowy < 0 || nowy >= l)
continue;
ans[nowx][nowy] = res+1;
bf.push({ nowx,nowy });
}
}
cout << ans[p][q] << endl;
}
return 0;
}
H - Oil Deposits
int n, m;
char a[105][105];
int d[4][2] = { -1,0,1,0,0,-1,0,1 };
void dfs(int x, int y)
{
a[x][y] = '*';
for(int i=-1;i<=1;i++)
for (int j = -1; j <= 1; j++)
{
int xx = x + i, yy = y + j;
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == '@')
dfs(xx, yy);
}
}
int main()
{
while (cin >> n >> m )
{
if (n == 0 && m == 0)
break;
int ans;
ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] == '@')
{
dfs(i, j);
ans++;
}
cout << ans<
I - Lake Counting
int n, m;
char a[105][105];
void dfs(int x, int y)
{
a[x][y] = '.';
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
int xx = x + i, yy = y + j;
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == 'W')
dfs(xx, yy);
}
}
}
int main()
{
int ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] == 'W')
{
dfs(i, j);
ans++;
}
cout << ans;
return 0;
}
J - 二叉树先序遍历
struct node {
int left, right;
}p[100005];
int n;
void solve(int x)
{
printf("%dn", x);
if (p[x].left)solve(p[x].left);
if (p[x].right)solve(p[x].right);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &p[i].left, &p[i].right);
solve(1);
return 0;
}
K - 迷宫（一）
int n, m;
int res[4][2] = { 0,-1,0,1,-1,0,1,0 };
int a, b, c, d;
char s[15][15];
int ss[15][15];
int flag = 0;
void dfs(int p, int q, int w, int y)
{
if (p == w && q == y)
{
flag = 1;
return;
}
for (int i = 0; i < 4; i++)
{
int xx = p + res[i][0], yy = q+res[i][1];
if (ss[xx][yy]==1||s[xx][yy]=='*' || xx > n || xx<1 || yy>m || yy < 1)
continue;
ss[xx][yy] = 1;
dfs(xx, yy,w,y);
ss[xx][yy] = 0;
}
return;
}
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
for (int j = 1; j <= m; j++)
{
cin >> s[i][j];
if (s[i][j] == 'S')
a = i, b = j;
if (s[i][j] == 'T')
c = i, d = j;
}
ss[a][b] = 1;
dfs(a, b, c, d);
if(flag)
cout << "yes";
else
cout << "no";
return 0;
}
L - 马走日
int n, m, a, b;
int c[10][10];
int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int ans;
void dfs(int x, int y,int step)
{
if (step == n * m)
{
ans++;
return;
}
else
{
for (int i = 0; i < 8; i++)
{
int xx = x + dx[i], yy = y + dy[i];
if (c[xx][yy]||xx < 0 || xx >= n || yy < 0 || yy >= m)
continue;
c[xx][yy] = 1;
dfs(xx, yy,step+1);
c[xx][yy] = 0;
}
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
ans = 0;
memset(c, 0, sizeof(c));
cin >> n >> m >> a >> b;
c[a][b] = 1;
dfs(a, b,1);
cout << ans << endl;
}
return 0;
}
M - 八皇后问题
int k;
int line[9], xie1[15], xie2[15];
int a[9][9], res;
void dfs(int step, int sum)
{
if (step > 7)
{
res = max(res, sum);
return;
}
for (int j = 0; j < 8; j++)
{
if (line[j] == 0 && xie1[step + j] == 0 && xie2[step - j + 7] == 0)
{
line[j] = xie1[step + j] = xie2[step - j + 7] = 1;
sum += a[step][j];
dfs(step + 1, sum);
line[j] = xie1[step + j] = xie2[step - j + 7] = 0;
sum -= a[step][j];
}
}
}
int main()
{
scanf("%d", &k);
while (k--)
{
memset(line, 0, sizeof(line));
memset(xie1, 0, sizeof(xie1));
memset(xie2, 0, sizeof(xie2));
memset(a, 0, sizeof(a));
for (int i = 0; i < 8; i++)
for (int j = 0; j < 8; j++)
scanf("%d", &a[i][j]);
res = 0;
dfs(0, 0);
cout << res << endl;
}
return 0;
}
N - 选数
int n, k;
int a[25];
int d[4][2] = { -1,0,1,0,0,-1,0,1 };
bool prime(int x)
{
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0)
return false;
return true;
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int s = 1 << n;
int ans = 0;
for (int i = 0; i < s; i++)
{
if (__builtin_popcount(i) == k)
{
int sum = 0;
for (int j = 0; j < n; j++)
{
if (i & (1 << j))
sum += a[j];
}
if (prime(sum))
ans++;
}
}
printf("%d", ans);
return 0;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）