比赛 20101116 评测结果 AATTTTTTTA
题目名称 剪切矩形 最终得分 30
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-16 10:59:37
显示代码纯文本
  1. #include <fstream>
  2.  
  3. #define I_F "rectangle.in"
  4. #define O_F "rectangle.out"
  5. #define MAX 1000
  6.  
  7. using namespace std;
  8.  
  9. long map[MAX][MAX];
  10. int n,m;
  11. long ans;
  12.  
  13. void Input();
  14. void Ycl();
  15. long Pd(int x1, int y1, int x2, int y2);
  16. void Search();
  17. void Output();
  18.  
  19. int main()
  20. {
  21. Input();
  22. Ycl();
  23. Search();
  24. Output();
  25. return 0;
  26. }
  27.  
  28. void Input()
  29. {
  30. ifstream fin(I_F);
  31. int i,j;
  32. char t;
  33. fin>>n>>m;
  34. for (i=0; i<n; i++)
  35. for (j=0; j<m; j++)
  36. {
  37. fin>>t;
  38. if (t=='*')
  39. map[i][j]=1;
  40. }
  41. fin.close();
  42. }
  43.  
  44. void Ycl()
  45. {
  46. int i,j;
  47. for (i=1; i<n; i++)
  48. map[i][0]+=map[i-1][0];
  49. for (j=1; j<m; j++)
  50. map[0][j]+=map[0][j-1];
  51. for (i=1; i<n; i++)
  52. for (j=1; j<m; j++)
  53. map[i][j]=map[i-1][j]+map[i][j-1]-map[i-1][j-1]+map[i][j];
  54. }
  55.  
  56. long Pd(int x1, int y1, int x2, int y2)
  57. {
  58. long t=map[x2][y2];
  59. if (x1>0)
  60. t-=map[x1-1][y2];
  61. if (y1>0)
  62. t-=map[x2][y1-1];
  63. if ((x1>0)&&(y1>0))
  64. t+=map[x1-1][y1-1];
  65. return t;
  66. }
  67.  
  68. void Search()
  69. {
  70. int i,j,k,l;
  71. for (i=0; i<n; i++)
  72. for (j=i; j<n; j++)
  73. for (k=0; k<m; k++)
  74. for (l=k; l<m; l++)
  75. if (Pd(i,k,j,l)==0)
  76. ans++;
  77. }
  78.  
  79. void Output()
  80. {
  81. ofstream fout(O_F);
  82. fout<<ans<<'\n';
  83. fout.close();
  84. }