Advertisement
Guest User

Untitled

a guest
Oct 17th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Lua 1.32 KB | None | 0 0
  1. local starts = {}; --store where each character is
  2. local grid = {}; --stores the grid of characters
  3.  
  4. --HANDLING INPUT
  5. local n = io.read("*number");
  6. local m = io.read("*number"); io.read("*line");
  7.  
  8. for i = 1, n do
  9.     local line = io.read("*line");
  10.     grid[i] = {};
  11.     for j = 1, line:len(), 2 do
  12.         local char = line:sub(j, j);
  13.         grid[i][j] = {char = char, x = i, y = (j+1)/2};
  14.  
  15.         if not starts[char] then
  16.             starts[char] = {};
  17.         end
  18.         table.insert(starts[char], {x = i, y = (j+1)/2});
  19.     end
  20. end
  21.  
  22. local scan = function(word)
  23.     local allowed;
  24.  
  25.     for i = 1, word:len() do
  26.         local letter = word:sub(i, i);
  27.         local validPos = starts[letter];
  28.         --letter is not in grid, return false
  29.         if not validPos then return false end
  30.  
  31.         local newAllowed = {};
  32.         local found = false;
  33.         for j = 1, #validPos do
  34.             local pos = validPos[j];
  35.             local reachable = not allowed or allowed[pos.x..":"..pos.y];
  36.             if reachable then
  37.                 found = true;
  38.                 newAllowed[(pos.x-1)..":"..(pos.y)] = true;
  39.                 newAllowed[(pos.x+1)..":"..(pos.y)] = true;
  40.                 newAllowed[(pos.x)..":"..(pos.y-1)] = true;
  41.                 newAllowed[(pos.x)..":"..(pos.y+1)] = true;
  42.             end
  43.         end
  44.         allowed = newAllowed;
  45.         if not found then return false end
  46.     end
  47.  
  48.     return true;
  49. end
  50.  
  51. for i = 1, m do
  52.     local line = io.read("*line");
  53.     if scan(line) then
  54.         print(line);
  55.     end
  56. end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement