import heapq

rows, cols = map(int, input("Grid rows and columns (at least 8 8): ").split())
if rows < 8 or cols < 8:
    raise ValueError("Use a grid of at least 8 by 8 cells.")
grid = [[0] * cols for _ in range(rows)]
print("Coordinates are zero-based: row column.")
obstacle_count = int(input("Number of obstacle cells: "))
if not 0 <= obstacle_count <= rows * cols:
    raise ValueError("Invalid obstacle count.")
for _ in range(obstacle_count):
    r, c = map(int, input("Obstacle row column: ").split())
    if not (0 <= r < rows and 0 <= c < cols):
        raise ValueError("Obstacle must be inside the grid.")
    grid[r][c] = 1
start = tuple(map(int, input("Start row column: ").split()))
goal = tuple(map(int, input("Goal row column: ").split()))
if len(start) != 2 or len(goal) != 2:
    raise ValueError("Enter exactly two coordinates for start and goal.")

def free(cell):
    r,c = cell
    return 0 <= r < rows and 0 <= c < cols and grid[r][c] == 0

def h(cell):
    return abs(cell[0]-goal[0]) + abs(cell[1]-goal[1])

if not free(start) or not free(goal):
    raise ValueError("Start and goal must be free cells inside the grid.")


queue = [(h(start), 0, start, [start])]
best_cost = {start: 0}
path = []
explored = 0
while queue:
    estimate, cost, cell, route = heapq.heappop(queue)
    if cost != best_cost[cell]:
        continue
    explored += 1
    if cell == goal:
        path = route
        break
    r,c = cell
    for next_cell in [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]:
        new_cost = cost + 1
        if free(next_cell) and new_cost < best_cost.get(next_cell, float("inf")):
            best_cost[next_cell] = new_cost
            heapq.heappush(queue,(new_cost+h(next_cell),new_cost,next_cell,route+[next_cell]))


for r in range(rows):
    line = []
    for c in range(cols):
        if (r,c) == start: symbol = "S"
        elif (r,c) == goal: symbol = "G"
        elif grid[r][c] == 1: symbol = "#"
        elif (r,c) in path: symbol = "*"
        else: symbol = "."
        line.append(symbol)
    print(" ".join(line))
if path:
    print("Path:", path)
    print("Path length in moves:", len(path)-1)
else:
    print("No valid path exists.")
print("Explored cells:", explored)
