https://ac.nowcoder.com/acm/contest/331/C
C++版本一
题解:
std
比如4*4,K=10的时候,很容易构造出:
....
xxx.
.xx.
....
于是得到了一种绕圈的想法。
但是在比如5*2,K=7中,绕圈法又遇到了阻碍,不如直走换边法,即
.x...
...x.
将这两种方法合并起来,即可以得到一种看起来还不错的解法。
如果能达到和以上算法同等优秀,就可以AC。
#include <bits/stdc++.h>
using namespace std;
//这份标程很不好看,建议阅读其他人的程序。
const int mn = 1005;
int n, m;
int k;
char s[mn][mn];
int calc(int n, int m) {
int ans = 0;
ans = n / 2 * (m + 1);
if (n % 2 == 1) ans += m;
return ans;
}
int lastx, lasty;
void genn() {
int ans = -1;
for (int i = 1; i <= n; i += 2) {
if (i / 2 % 2 == 0) {
for (int j = 1; j <= m; j++) {
s[i][j] = '.';
ans++;
if (ans == k) {
lastx = i, lasty = j;
return;
}
}
s[i + 1][m] = '.';
ans++;
if (ans == k) {
lastx = i + 1, lasty = m;
return;
}
} else {
for (int j = m; j; j--) {
s[i][j] = '.';
ans++;
if (ans == k) {
lastx = i, lasty = j;
return;
}
}
s[i + 1][1] = '.';
ans++;
if (ans == k) {
lastx = i + 1, lasty = 1;
return;
}
}
}
}
void genm() {
int ans = -1;
for (int i = 1; i <= m; i += 2) {
if (i / 2 % 2 == 0) {
for (int j = 1; j <= n; j++) {
s[j][i] = '.';
ans++;
if (ans == k) {
lastx = j, lasty = i;
return;
}
}
s[n][i + 1] = '.';
ans++;
if (ans == k) {
lastx = n, lasty = i + 1;
return;
}
} else {
for (int j = n; j; j--) {
s[j][i] = '.';
ans++;
if (ans == k) {
lastx = j, lasty = i;
return;
}
}
s[1][i + 1] = '.';
ans++;
if (ans == k) {
lastx = 1, lasty = i + 1;
return;
}
}
}
}
void app() {
int u, d, l, r;
u = 3, l = 1;
d = n, r = m;
int x = 1, y = 1;
int c = 0;
int step = 1;
while (step) {
if (c % 4 == 0) { // right
step = max(min(k, r - y), 0);
for (int i = y; i <= y + step; i++) s[x][i] = '.';
y += step;
r -= 2;
} else if (c % 4 == 1) { // down
step = max(min(k, d - x), 0);
for (int i = x; i <= x + step; i++) s[i][y] = '.';
x += step;
d -= 2;
} else if (c % 4 == 2) { // left
step = max(0, min(k, y - l));
for (int i = y; i >= y - step; i--) s[x][i] = '.';
y -= step;
l += 2;
} else if (c % 4 == 3) { // up
step = max(0, min(k, x - u));
for (int i = x; i >= x - step; i--) s[i][y] = '.';
x -= step;
u += 2;
}
k -= step;
c++;
}
lastx = x, lasty = y;
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) s[i][j] = 'x';
}
if (max(calc(n, m), calc(m, n)) - 1 >= k) {
if (calc(n, m) >= calc(m, n)) genn();
else genm();
}
else app();
printf("%d %d\n%d %d\n", 1, 1, lastx, lasty);
for (int i = 1; i <= n; i++) puts(s[i] + 1);
return 0;
}
C++版本二
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
int read(){
int x = 0,f = 1;
char c = getchar();
while (c<'0' || c>'9'){
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0'&&c <= '9'){
x = x * 10 + c - '0';
c = getchar();
}
return x*f;
}
const double eps = 1e-9;
const int maxn = 1010;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,K;
const int a[4][2] = {0,1,0,-1,1,0,-1,0};
char MAP[maxn][maxn];
char MAP2[maxn][maxn];
bool vis[maxn][maxn];
struct node{
int x,y,num;
node(int x,int y,int num):x(x),y(y),num(num){}
};
bool check(node a){
return 1 <= a.x && a.x <= N && 1 <= a.y && a.y <= M && MAP[a.x][a.y] == '.' && !vis[a.x][a.y];
}
void BFS(){
queue<node>Q;
Q.push(node(1,1,0));
vis[1][1] = 1;
while(!Q.empty()){
node u = Q.front(); Q.pop();
if(u.num == K){
printf("%d %d\n",u.x,u.y);
return;
}
for(int i = 0; i < 4; i ++){
node h = node(u.x + a[i][0],u.y + a[i][1],u.num + 1);
if(!check(h)) continue;
Q.push(h);
vis[h.x][h.y] = 1;
}
}
}
int main(){
Sca3(N,M,K);
int ans = 0;
for(int i = 1; i <= N ; i ++){
for(int j = 1; j <= M ; j ++){
if(i & 1){
MAP[i][j] = '.';
ans++;
}
else MAP[i][j] = 'x';
}
}
for(int i = 2; i <= N ;i += 4){
MAP[i][M] = '.';
ans++;
}
for(int i = 4; i <= N; i += 4){
MAP[i][1] = '.';
ans++;
}
for(int i = 1; i <= M ; i ++){
for(int j = 1; j <= N ; j ++){
if(i & 1){
MAP2[j][i] = '.';
ans--;
}
else MAP2[j][i] = 'x';
}
}
for(int i = 2; i <= M ; i += 4){
MAP2[N][i] = '.';
ans--;
}
for(int i = 4; i <= M ; i += 4){
MAP2[1][i] = '.';
ans--;
}
if(ans < 0){
For(i,1,N) For(j,1,M) MAP[i][j] = MAP2[i][j];
}
printf("1 1\n");
BFS();
for(int i = 1; i <= N ; i ++){
for(int j = 1; j <= M ; j++){
printf("%c",MAP[i][j]);
}
puts("");
}
return 0;
}