E-Circuit Is Now on Sale!
Source: aizu

E-Circuit Is Now on Sale!

Are you looking for math education tools for your children? Then, why not try this amazing product, E-circuit? This is the best toy to learn two-dimensional geometry, logic, and arithmetic!

The E-circuit consists of a grid space with a bunch of square blocks, called units. Each unit perfectly fits into a grid cell. They have some input and/or output terminals to transfer integer values. When a number of units are appropriately placed in the grid, they form a tree representing a mathematical formula.

The units have different functionalities, each represented by a single character as follows.

Digit (‘0’ to ‘9’): These units have one output terminal. Each of them sends the integer value indicated by the digit to its output.
Connector (‘#’): These units have one input terminal and one output terminal. Each of them receives an integer value from its input and sends the value to its output without making any changes.
Operator (‘+’, ‘-’, ‘*’, ‘/’): These units have two input terminals and one output terminal, do the following calculations on the values received from their inputs, and send the results to their outputs.
‘+’ operators compute the sum of the two input values.
‘-’ operators compute the difference of the two input values, the larger one subtracted by the smaller one.
‘*’ operators compute the product of the two input values.
‘/’ operators compute the quotient of the input values, the larger one divided by the smaller one, truncating the fraction, if any.
Printer (‘P’): The printer has one input terminal and displays the input value. There should be exactly one printer unit on the grid.

Two cells are adjacent if they share an edge. When two units are placed on adjacent cells, they are connected by using an input terminal of one unit and an output terminal of the other.

You are given an appropriate placement of units in which the units form a single tree representing a mathematical formula. A formal description of such a placement will be given in the Input section.

Your task is to calculate the value the printer displays for the given unit placement.

Input

The input consists of a single test case of the following format.

$n$ $m$
$x_{1,1}$ ... $x_{1,m}$
$\vdots$
$x_{n,1}$ ... $x_{n,m}$


The first two integers $n$ and $m$ ($1 \leq n \leq 50, 1 \leq m \leq 50$) mean that the grid has cells arranged in an $n \times m$ matrix. The following $n$ lines describe the placement of units. The character $x_{i,j}$ ($1 \leq i \leq n, 1 \leq j \leq m$) specifies the unit on the cell $i$-th from the top and $j$-th from the left. Each character either represents the unit functionality, as described in the problem statement, or is the character ‘.’, meaning that the cell is empty.

It is guaranteed that the units are placed appropriately, that is,

the number of adjacent units of each unit equals the total number of its input and output terminals,
the total number of input terminals and that of output terminals of all the units are equal, and
all the units belong to the printer tree: a unit belongs to the printer tree if and only if it is the printer or adjacent to another unit belonging to the printer tree.

It is also guaranteed that input values of ‘/’ operators are not zero and no units have an output value larger than $10^{18}$.

Output

Output a line containing the displayed value.

Sample Input 1
6 8
3.......
#....P..
#....#.2
#.###*#+
##-....#
..1...4#

Sample Output 1
12

Sample Input 2
4 3
.4.
./P
9*.
.#7

Sample Output 2
15

Sample Input 3
5 11
8...8.....8
#.###...###
#.#...P.#..
#**##-*+/##
.4...3.0..1

Sample Output 3
2024


C++ solution:
// AOJ #1459
// E-Circuit Is Now on Sale! 2025.1.14

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point {
    int row, col;
};

vector<string> grid;
int n, m;

// Direction vectors for adjacency (up, down, left, right)
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

// Function to check if a cell is valid and within bounds
bool isValid(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < m && grid[r][c] != '.';
}

// DFS to calculate the value of the tree
ll dfs(int r, int c) {
    char unit = grid[r][c];
    grid[r][c] = '.'; // Mark visited

    if (isdigit(unit)) {
        return unit - '0';
    } else if (unit == 'P') {
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (isValid(nr, nc)) {
                return dfs(nr, nc);
            }
        }
    } else if (unit == '#') {
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (isValid(nr, nc)) {
                return dfs(nr, nc);
            }
        }
    } else if (unit == '+' || unit == '-' || unit == '*' || unit == '/') {
        ll values[2] = {0};
        int count = 0;
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (isValid(nr, nc)) {
                values[count++] = dfs(nr, nc);
            }
        }
        if (count == 2) {
            if (unit == '+') return values[0] + values[1];
            if (unit == '-') return abs(values[0] - values[1]);
            if (unit == '*') return values[0] * values[1];
            if (unit == '/') return values[0] > values[1] ? values[0] / values[1] : values[1] / values[0];
        }
    }

    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    grid.resize(n);
    Point printer;

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'P') {
                printer.row = i, printer.col = j;
            }
        }
    }

    ll result = dfs(printer.row, printer.col);
    cout << result << endl;

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	scanner.Scan()
	m, _ := strconv.Atoi(scanner.Text())

	grid := make([][]byte, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		grid[i] = []byte(scanner.Text())
	}

	var rootI, rootJ int
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if grid[i][j] == 'P' {
				rootI, rootJ = i, j
			}
		}
	}

	var dfs func(i, j int, pi, pj int) int
	dfs = func(i, j int, pi, pj int) int {
		var children []int
		directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
		for _, dir := range directions {
			ni, nj := i+dir[0], j+dir[1]
			if ni < 0 || ni >= n || nj < 0 || nj >= m {
				continue
			}
			if grid[ni][nj] == '.' {
				continue
			}
			if ni == pi && nj == pj {
				continue
			}
			children = append(children, dfs(ni, nj, i, j))
		}

		c := grid[i][j]
		switch c {
		case 'P':
			if len(children) != 1 {
				panic("Printer must have exactly one child")
			}
			return children[0]
		case '#':
			if len(children) != 1 {
				panic("Connector must have exactly one child")
			}
			return children[0]
		case '+', '-', '*', '/':
			if len(children) != 2 {
				panic("Operator must have exactly two children")
			}
			sort.Ints(children)
			a, b := children[0], children[1]
			switch c {
			case '+':
				return a + b
			case '-':
				return b - a
			case '*':
				return a * b
			case '/':
				return b / a
			}
		default:
			if c >= '0' && c <= '9' {
				if len(children) != 0 {
					panic("Digit must have no children")
				}
				return int(c - '0')
			}
			panic("Unknown unit type")
		}
		return 0
	}

	result := dfs(rootI, rootJ, -1, -1)
	fmt.Println(result)
}

Java solution:
import java.util.*;

public class Main {
    static int N, M;
    static char[][] grid;
    static int[] root = new int[2];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine(); // consume the rest of the line
        grid = new char[N][M];
        for (int i = 0; i < N; i++) {
            String line = sc.nextLine();
            for (int j = 0; j < M; j++) {
                grid[i][j] = line.charAt(j);
                if (grid[i][j] == 'P') {
                    root[0] = i;
                    root[1] = j;
                }
            }
        }
        long result = dfs(root[0], root[1], -1, -1);
        System.out.println(result);
    }

    static long dfs(int i, int j, int pi, int pj) {
        List<Long> children = new ArrayList<>();
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] dir : directions) {
            int ni = i + dir[0];
            int nj = j + dir[1];
            if (ni < 0 || ni >= N || nj < 0 || nj >= M) continue;
            if (grid[ni][nj] == '.') continue;
            if (ni == pi && nj == pj) continue;
            children.add(dfs(ni, nj, i, j));
        }
        char c = grid[i][j];
        if (c == 'P' || c == '#') {
            return children.get(0);
        } else if (Character.isDigit(c)) {
            return c - '0';
        } else {
            Collections.sort(children);
            long a = children.get(0);
            long b = children.get(1);
            switch (c) {
                case '+':
                    return a + b;
                case '-':
                    return b - a;
                case '*':
                    return a * b;
                case '/':
                    return b / a;
                default:
                    return 0;
            }
        }
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let N, M;
let grid = [];
let printerPos = null;

function main() {
    let lineCount = 0;
    
    rl.on('line', (line) => {
        if (lineCount === 0) {
            [N, M] = line.trim().split(' ').map(Number);
            lineCount++;
        } else {
            grid.push(line.trim());
            lineCount++;
            
            if (lineCount === N + 1) {
                rl.close();
                processGrid();
            }
        }
    });
}

function processGrid() {
    // Find printer position
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (grid[i][j] === 'P') {
                printerPos = {i, j};
                break;
            }
        }
        if (printerPos) break;
    }
    
    if (!printerPos) {
        console.log(0);
        return;
    }
    
    // Evaluate the circuit
    try {
        const result = evaluateCircuit(printerPos, null);
        console.log(result.toString());
    } catch (e) {
        console.log(0);
    }
}

function evaluateCircuit(pos, parent) {
    const {i, j} = pos;
    const cell = grid[i][j];
    const neighbors = [];
    
    // Check all four directions
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    for (const [di, dj] of directions) {
        const ni = i + di;
        const nj = j + dj;
        
        if (ni < 0 || ni >= N || nj < 0 || nj >= M) continue;
        if (grid[ni][nj] === '.') continue;
        if (parent && ni === parent.i && nj === parent.j) continue;
        
        neighbors.push({i: ni, j: nj});
    }
    
    if (cell === 'P' || cell === '#') {
        if (neighbors.length !== 1) throw new Error("Invalid circuit");
        return evaluateCircuit(neighbors[0], pos);
    } else if (/^\d$/.test(cell)) {
        if (neighbors.length !== 0) throw new Error("Invalid circuit");
        return parseInt(cell);
    } else {
        if (neighbors.length !== 2) throw new Error("Invalid circuit");
        const [a, b] = neighbors.map(neighbor => evaluateCircuit(neighbor, pos));
        const [val1, val2] = [a, b].sort((x, y) => x - y);
        
        switch (cell) {
            case '+': return val1 + val2;
            case '-': return val2 - val1;
            case '*': return val1 * val2;
            case '/': 
                if (val1 === 0) throw new Error("Division by zero");
                return Math.floor(val2 / val1);
            default: throw new Error("Unknown operator");
        }
    }
}

main();

Python solution:
import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
X = [input() for i in range(N)]
root = (-1, -1)
for i in range(N):
    for j in range(M):
        if X[i][j] == "P":
            root = (i, j)


def dfs(u, p):
    i, j = u
    l = []
    for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if not 0 <= i + di < N:
            continue
        if not 0 <= j + dj < M:
            continue
        if X[i + di][j + dj] == ".":
            continue
        if (i + di, j + dj) == p:
            continue
        l.append(dfs((i + di, j + dj), u))
    if X[i][j] == "P" or X[i][j] == "#":
        assert len(l) == 1
        return l[0]
    elif X[i][j].isdigit():
        assert len(l) == 0
        return int(X[i][j])
    else:
        assert len(l) == 2
        l.sort()
        if X[i][j] == "+":
            return l[0] + l[1]
        elif X[i][j] == "-":
            return l[1] - l[0]
        elif X[i][j] == "*":
            return l[0] * l[1]
        else:
            return l[1] // l[0]


print(dfs(root, (-1, -1)))

Ruby solution:
require 'set'

# Read input dimensions
n, m = gets.split.map(&:to_i)
grid = []
n.times { grid << gets.chomp }

# Find the printer (P) position
root = nil
grid.each_with_index do |row, i|
  j = row.index('P')
  if j
    root = [i, j]
    break
  end
end

def evaluate_expression(grid, position, parent, rows, cols)
  i, j = position
  neighbors = []
  
  # Check all four possible directions
  [[-1, 0], [1, 0], [0, -1], [0, 1]].each do |di, dj|
    ni, nj = i + di, j + dj
    # Skip if out of bounds or empty cell
    next unless ni.between?(0, rows-1) && nj.between?(0, cols-1)
    next if grid[ni][nj] == '.'
    # Skip parent node to avoid cycles
    next if [ni, nj] == parent
    
    neighbors << [ni, nj]
  end
  
  # Recursively evaluate all neighbors
  values = neighbors.map { |pos| evaluate_expression(grid, pos, position, rows, cols) }
  
  # Process current cell based on its type
  case grid[i][j]
  when 'P', '#'  # Printer or connector - pass through value
    values.first
  when /^[0-9]$/ # Digit unit
    grid[i][j].to_i
  when '+'       # Addition
    values.sum
  when '-'       # Subtraction (larger - smaller)
    a, b = values.minmax
    b - a
  when '*'       # Multiplication
    values.inject(:*)
  when '/'       # Division (larger / smaller)
    a, b = values.minmax
    b / a
  else
    raise "Invalid unit type: #{grid[i][j]}"
  end
end

# Start evaluation from the printer position
puts evaluate_expression(grid, root, nil, n, m)