fork download
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("sse4")
  3. #include <cstdio>
  4. #include <cstring>
  5. using namespace std;
  6. int r,c,m;
  7. const int N = 502, M = 5000;
  8. bool reach[N][N],tmp[N][N],sea[N][N];
  9. char grid[N][N], msg[M];
  10. int main(){
  11. scanf("%d %d %d",&r,&c,&m);
  12. for(int i = 1; i <= r; ++i)
  13. scanf("%s",grid[i]+1);
  14. scanf("%s",msg);
  15. for(int i = 1; i <= r; ++i)
  16. for(int j = 1; j <= c; ++j){
  17. sea[i][j] = grid[i][j] == '.';
  18. reach[i][j] = grid[i][j] == '.';
  19. }
  20. for(char w : msg){
  21. if(w == 'W')
  22. for(int i = 1; i <= r; ++i){
  23. for(int j = 1; j <= c-1; ++j)
  24. reach[i][j] = reach[i][j+1] & sea[i][j];
  25. reach[i][c] = 0;
  26. }
  27. if(w == 'E')
  28. for(int i = 1; i <= r; ++i){
  29. for(int j = c; j > 1; --j)
  30. reach[i][j] = reach[i][j-1] & sea[i][j];
  31. reach[i][1] = 0;
  32. }
  33. if(w == 'N'){
  34. for(int i = 1; i <= r-1; ++i)
  35. for(int j = 1; j <= c; ++j)
  36. reach[i][j] = reach[i+1][j] & sea[i][j];
  37. memset(reach[r], 0, sizeof reach[0]);
  38. }
  39. if(w == 'S'){
  40. for(int i = r; i > 1; --i)
  41. for(int j = 1; j <= c; ++j)
  42. reach[i][j] = reach[i-1][j] & sea[i][j];
  43. memset(reach[1], 0, sizeof reach[0]);
  44. }
  45. if(w == '?'){
  46. for(int i = 1; i <= r; ++i)
  47. for(int j = 1; j <= c; ++j)
  48. tmp[i][j] = (reach[i-1][j]|reach[i+1][j]|reach[i][j-1]|reach[i][j+1])&sea[i][j];
  49. memmove(reach, tmp, sizeof tmp);
  50. }
  51. }
  52. int ans = 0;
  53. for(int i = 1; i <= r; ++i)
  54. for(int j = 1; j <= c; ++j)
  55. ans += reach[i][j];
  56. printf("%d\n",ans);
  57. }
  58.  
Success #stdin #stdout 0s 16232KB
stdin
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
stdout
22