{"problem":{"name":"F2 - Reachable Cells","description":{"content":"**Problem F and F2 are the same problem, but with different constraints and time limits.** We have a board divided into $N$ horizontal rows and $N$ vertical columns of square cells. The cell at the $i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":9000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc028_f2"},"statements":[{"statement_type":"Markdown","content":"**Problem F and F2 are the same problem, but with different constraints and time limits.**\nWe have a board divided into $N$ horizontal rows and $N$ vertical columns of square cells. The cell at the $i$\\-th row from the top and the $j$\\-th column from the left is called Cell $(i,j)$. Each cell is either empty or occupied by an obstacle. Also, each empty cell has a digit written on it. If $A_{i,j}=$ `1`, `2`, ..., or `9`, Cell $(i,j)$ is empty and the digit $A_{i,j}$ is written on it. If $A_{i,j}=$ `#`, Cell $(i,j)$ is occupied by an obstacle.\nCell $Y$ is _reachable_ from cell $X$ when the following conditions are all met:\n\n*   Cells $X$ and $Y$ are different.\n*   Cells $X$ and $Y$ are both empty.\n*   One can reach from Cell $X$ to Cell $Y$ by repeatedly moving right or down to an adjacent empty cell.\n\nConsider all pairs of cells $(X,Y)$ such that cell $Y$ is reachable from cell $X$. Find the sum of the products of the digits written on cell $X$ and cell $Y$ for all of those pairs.\n\n## Constraints\n\n*   $1 \\leq N \\leq 1500$\n*   $A_{i,j}$ is one of the following characters: `1`, `2`, ... `9` and `#`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_{1,1}A_{1,2}...A_{1,N}$\n$A_{2,1}A_{2,2}...A_{2,N}$\n$:$\n$A_{N,1}A_{N,2}...A_{N,N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc028_f2","tags":[],"sample_group":[["2\n11\n11","5\n\nThere are five pairs of cells $(X,Y)$ such that cell $Y$ is reachable from cell $X$, as follows:\n\n*   $X=(1,1)$, $Y=(1,2)$\n*   $X=(1,1)$, $Y=(2,1)$\n*   $X=(1,1)$, $Y=(2,2)$\n*   $X=(1,2)$, $Y=(2,2)$\n*   $X=(2,1)$, $Y=(2,2)$\n\nThe product of the digits written on cell $X$ and cell $Y$ is $1$ for all of those pairs, so the answer is $5$."],["4\n1111\n11#1\n1#11\n1111","47"],["10\n76##63##3#\n8445669721\n75#9542133\n3#285##445\n749632##89\n2458##9515\n5952578#77\n1#3#44196#\n4355#99#1#\n#298#63587","36065"],["10\n4177143673\n7#########\n5#1716155#\n6#4#####5#\n2#3#597#6#\n6#9#8#3#5#\n5#2#899#9#\n1#6#####6#\n6#5359657#\n5#########","6525"]],"created_at":"2026-03-03 11:01:13"}}