A - Cakeminator
简单的模拟。。就这我还写了好久。。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int r,c;
char s[15][15];
bool used[15][15];
char cc;
int sum;
int shu;
int main()
{
scanf("%d%d",&r,&c);
memset(used,0,sizeof(used));
sum = 0;
for(int i=0;i<r;i++)
{
cc = getchar();
for(int j=0;j<c;j++)
{
s[i][j] = getchar();
}
}
int q = 0;
for(int i=0;i<r;i++)
{
shu = 0;
q = 0;
for(int j=0;j<c;j++)
{
if(s[i][j] == '.'&&used[i][j] == 0)
{
shu++;
}
else if(s[i][j] != '.')
{
q = 1;
break;
}
}
if(q == 0)
{
sum += shu;
for(int j=0;j<c;j++)
{
used[i][j] = 1;
}
}
}
for(int i=0;i<c;i++)
{
shu = 0;
q = 0;
for(int j=0;j<r;j++)
{
if(s[j][i] == '.'&&used[j][i] == 0)
{
shu++;
}
else if(s[j][i] != '.')
{
q = 1;
break;
}
}
if(q == 0)
{
sum += shu;
for(int j=0;j<c;j++)
{
used[j][i] = 1;
}
}
}
printf("%d\n",sum);
return 0;
}
因为0<m<n/2，肯定会有未连接的空点，找空点就行了。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
int s[1005];
int main()
{
int x,y,q;
memset(s,0,sizeof(s));
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
s[x]++;
s[y]++;
}
for(int i=1;i<=n;i++)
{
if(s[i] == 0)
{
q = i;
break;
}
}
printf("%d\n",n-1);
for(int i=1;i<=n;i++)
{
if(i != q)
{
printf("%d %d\n",i,q);
}
}
return 0;
}
一开始以为必须要所有选择的点没有交集，结束就只是单纯的搜索行搜索列，还因为之前的误解写成了DFS,伤心啊。。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,q;
char s[105][105];
bool used[105][105];
int dx[105];
int dy[105];
int shu;
char c;
void dfsh(int xx)
{
for(int i=1; i<=n; i++)
{
if(s[xx][i] == '.'&&shu != n)
{
if(shu != n)
{
dx[shu] = xx;
dy[shu] = i;
shu++;
dfsh(xx+1);
}
}
}
if(shu != n)
{
shu--;
}
}
void dfsl(int xx)
{
for(int i=1; i<=n; i++)
{
if(s[i][xx] == '.'&&shu != n)
{
if(shu != n)
{
dx[shu] = i;
dy[shu] = xx;
shu++;
dfsl(xx+1);
}
}
}
if(shu != n)
{
shu--;
}
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
c = getchar();
for(int j=1; j<=n; j++)
{
s[i][j] = getchar();
}
}
shu = 0;
dfsh(1);
if(shu < n)
{
shu = 0;
dfsl(1);
}
if(shu == n)
{
for(int i=0; i<n; i++)
{
printf("%d %d\n",dx[i],dy[i]);
}
}
else
{
printf("-1\n");
}
return 0;
}
从终点E开始往回搜索查距离的简单BFS，比赛的时候没想到这么弄，写成DFS直接TLE了。。
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
char s[1005][1005];
bool used[1005][1005];
char c;
int xf[5] = {1,0,-1,0};
int yf[5] = {0,-1,0,1};
int sx,sy,swei,ex,ey,l,ll,q;
struct node
{
int dx,dy,dshu,dwei;
}d[1000005];
int shu;
bool cmp(node x,node y)
{
return x.dwei < y.dwei;
}
void bfs(int xx,int yy)
{
l++;
used[xx][yy] = 1;
for(int i=0;i<4;i++)
{
if(s[xx+xf[i]][yy+yf[i]] != 'T'&&used[xx+xf[i]][yy+yf[i]]==0)
{
if(s[xx+xf[i]][yy+yf[i]] == 'E')
{
if(l < ll)
{
ll = l;
}
}
else
{
dfs(xx+xf[i],yy+yf[i]);
}
}
}
l--;
used[xx][yy] = 0;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=1001;i++)
{
for(int j=0;j<=1001;j++)
{
used[i][j] = 1;
}
}
for(int i=1;i<=n;i++)
{
c = getchar();
for(int j=1;j<=m;j++)
{
s[i][j] = getchar();
}
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<s[i][j];
}
cout<<endl;
}*/
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
l = 0;
ll = 1000000;
if(s[i][j] == 'S')
{
for(int ii=1;ii<=n;ii++)
{
for(int jj = 1;jj<=m;jj++)
{
used[ii][jj] = 0;
}
}
dfs(i,j);
sx = i;
sy = j;
swei = ll;
//cout<<ll<<endl<<"aaaaaaaa"<<endl;
}
else if(s[i][j] > '0' && s[i][j] <= '9')
{
//cout<<s[i][j]<<endl;
//cout<<i<<' '<<j<<endl;
for(int ii=1;ii<=n;ii++)
{
for(int jj = 1;jj<=m;jj++)
{
used[ii][jj] = 0;
}
}
dfs(i,j);
d[shu].dx = i;
d[shu].dy = j;
d[shu].dwei = ll;
//cout<<ll<<endl;
//cout<<i<<' '<<j<<endl;
int aa = s[i][j] - '0';
d[shu].dshu = aa;
//cout<<d[shu].dwei<<endl;
shu++;
}
}
}
sort(d,d+shu,cmp);
int i = 0;
int sum = 0;
while(i < shu&&d[i].dwei <= swei)
{
sum += d[i].dshu;
i++;
}
printf("%d\n",sum);
return 0;
}