这题MLE了555(自从做了哈希的题来就经常和MLE打交道)……求助求助!
第一次提交:
#include <iostream>
using namespace std;
int n,m,k,x[505],y[505],ans;
bool vis[20005][20005];
int main()
{
cin >> n >> m >> k;
for(int i=0;i<k;i++)
{
cin >> x[i] >> y[i];
for(int j=0;j<m;j++)
{
vis[x[i]-1][j]=1;
}
for(int j=0;j<n;j++)
{
vis[j][y[i]-1]=1;
}
for(int j=x[i]-1,k=y[i]-1;j>=0&&k>=0;j--,k--)
{
vis[j][k]=1;
}
for(int j=x[i]-1,k=y[i]-1;j>=0&&k<m;j--,k++)
{
vis[j][k]=1;
}
for(int j=x[i]-1,k=y[i]-1;j<n&&k>=0;j++,k--)
{
vis[j][k]=1;
}
for(int j=x[i]-1,k=y[i]-1;j<n&&k<m;j++,k++)
{
vis[j][k]=1;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(vis[i][j]==0)
{
ans++;
}
}
}
cout << ans;
return 0;
}
第二次提交:
#include <iostream>
#include <map>
using namespace std;
struct a
{
int b,c;
bool operator < (const a d) const
{
return (b==d.b)?(c<d.c):(b<d.b);
}
};
map <a,bool> vis;
a d;
int n,m,k,x[505],y[505],ans;
int main()
{
cin >> n >> m >> k;
for(int i=0;i<k;i++)
{
cin >> x[i] >> y[i];
for(int j=0;j<m;j++)
{
d.b=x[i]-1;
d.c=j;
vis[d]=1;
}
for(int j=0;j<n;j++)
{
d.b=j;
d.c=y[i]-1;
vis[d]=1;
}
for(int j=x[i]-1,k=y[i]-1;j>=0&&k>=0;j--,k--)
{
d.b=j;
d.c=k;
vis[d]=1;
}
for(int j=x[i]-1,k=y[i]-1;j>=0&&k<m;j--,k++)
{
d.b=j;
d.c=k;
vis[d]=1;
}
for(int j=x[i]-1,k=y[i]-1;j<n&&k>=0;j++,k--)
{
d.b=j;
d.c=k;
vis[d]=1;
}
for(int j=x[i]-1,k=y[i]-1;j<n&&k<m;j++,k++)
{
d.b=j;
d.c=k;
vis[d]=1;
}
}
cout << n*m-vis.size();
return 0;
}
两次都MLE了555……