top of page

CCC 2020 S2 or J5: Escape Room

Updated: Jun 27, 2020

Perform a depth-first search (DFS) on the cells. There areN2cells and individually finding the factors of each number.

For a faster solution, observe that when the cell at

(i,j) has value v, a cell of product i⋅j can reach a cell of product

v. Let us add an edge from node i⋅j to node v, then j⋅i also can do it.


class cell:
    def __init__(self, x, y):
        self.x = x
        self.y = y


N = int(input())
M = int(input())
P = N*M
N += 1
M += 1

list1 = []
visited = []
#rlist = [0]*1000000
curlist = []
vcur = []
stacklist=[]
for i in range(M):
    curlist.append(0)
    vcur.append(True)
list1.append(curlist)
visited.append(vcur)

for i in range(N-1):
    curlist1 = [0]
    vcur1 = [True]
    S = input().split()
    for j in range(M-1):
        curlist1.append(int(S[j]))
        vcur1.append(False)
    list1.append(curlist1)
    visited.append(vcur1)

def handlexy(x1, y1):
    if x1 < N and y1 < M:
        if not visited[x1][y1]:
            if P == list1[x1][y1]:
                return True
            visited[x1][y1] = True
            stacklist.append(cell(x1, y1))
    if x1 < M and y1 < N:
        if not visited[y1][x1]:
            visited[y1][x1] = True
            if P == list1[y1][x1]:
                return True
            stacklist.append(cell(y1, x1))
    return False

def dfs2():
    if N-1 == 1 and M-1 == 1:
        return True
    if P == list1[1][1]:
        return True
    fn = cell(1,1)

    stacklist.append(fn)
    visited[1][1] = True
    while len(stacklist) > 0:
        cur = stacklist[-1]
        stacklist.pop()
        x = cur.x
        y = cur.y
        n = list1[x][y]

        start = int(n/(M-1))
        if start == 0:
            start = 1
        if start > 1:
            start -= 1
        end = N
        if end > n:
            end = n + 1
        i = start
        j = end
        while i <= j:
            if i < N:
                if n % i == 0:
                    x1 = i
                    y1 = int(n / i)
                    if handlexy(x1, y1):
                        return True
                    j = y1
            i += 1

    return False

if dfs2():
    print("yes")
else:
    print("no")

Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

コメント


bottom of page