fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <stdio.h>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <string>
  7. #include <assert.h>
  8. #include <ctype.h>
  9. #include <limits.h>
  10. #include <math.h>
  11. #include <stdlib.h>
  12. #include <string.h>
  13. #include <time.h>
  14. #include <bitset>
  15. #include <deque>
  16. #include <map>
  17. #include <queue>
  18. #include <set>
  19. #include <sstream>
  20. using namespace std;
  21. bool can[26];
  22. int n, m, k, q, res = 0;
  23. char key[31][31];
  24. char text[1000000];
  25. vector<pair<int, int>> posKey[26], shift;
  26.  
  27. int dist(int i, int j, int shr, int shc)
  28. {
  29. 	return (i - shr)*(i - shr) + (j - shc)*(j - shc);
  30. }
  31.  
  32. bool check(int i, int j)
  33. {
  34. 	for (int w = 0;w < shift.size();w++)
  35. 	{
  36. 		int dis = dist(i, j, shift[w].first, shift[w].second);
  37. 		if (dis <= k*k)
  38. 			return true;
  39. 	}
  40. 	return false;
  41. }
  42.  
  43.  
  44. int main()
  45.  
  46. {
  47. 	scanf("%d%d%d", &n, &m, &k);
  48. 	for (int i = 0;i < n; i++)              // keyboard keys
  49. 		scanf("%s", key[i]);
  50.  
  51.  
  52.  
  53. 	for (int i = 0;i<n;i++) 
  54. 		for (int j = 0;j < m;j++)
  55. 		{
  56. 			if (key[i][j] == 'S')
  57. 				shift.push_back(make_pair(i, j));                          // position of each key
  58. 			else
  59. 				posKey[key[i][j] - 'a'].push_back(make_pair(i, j));
  60. 		}
  61.  
  62.  
  63.  
  64.  
  65. 	for (int i = 0;i<26; i++)
  66. 		for (int j = 0;j <posKey[i].size() && !can[i]; j++)
  67. 		{                                                                         //check of each key if can press on it with one hand
  68. 			can[i] = can[i] | check(posKey[i][j].first, posKey[i][j].second);
  69. 		}
  70.  
  71.  
  72.  
  73. 	scanf("%d%s", &q, text);
  74. 	for (int i = 0;i < q;i++)
  75. 	{
  76. 		if (islower(text[i]))
  77. 		{
  78. 			if (posKey[text[i] - 'a'].empty())
  79. 			{
  80. 				res = -1;
  81. 				break;
  82. 			}
  83. 		}
  84. 		else
  85. 		{
  86. 			text[i] = tolower(text[i]);
  87.  
  88. 			if (shift.empty() || posKey[text[i] - 'a'].empty())
  89. 			{
  90. 				res = -1;
  91. 				break;
  92.  
  93. 			}
  94.  
  95. 			if (!can[text[i] - 'a'])
  96. 				++res;
  97. 		}
  98. 	}
  99. 	printf("%d", res);
  100.  
  101. 	return 0;
  102. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bnNQMI
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!