Problem:

Dungeon

Bob is playing a popular game called "Dungeon". The game is played on a rectangular board consisting of W &times;  H squares. Each square is identified with its column and row number, thus the square located in the x-th column and the y-th row is represented as (x, y). The left-most square in the top row is (0, 0) and the right-most square in the bottom row is (W-1, H-1).

  Bob moves a character "BomBom" to clear the game. BomBom is initially located at (0, 0). The game is won if Bob successfully destroys all the enemy characters on the board by manipulating BomBom cleverly. The enemy characters are fixed on specific squares, and Bob can manipulate BomBom using the following two operations any number of times.

 One-square movement in the up, down, left, or right direction within the board

 Using a bomb, eliminate all the enemy characters that are located in the same column and row as that of BomBom

BomBom consumes a Cost when it moves from one square to another. BomBom can use a bomb any number of times without consuming a Cost. Use of a bomb has no effect on BomBom’s behavior and it can move even to a square where an enemy character is located.

Given the board size and enemy information, make a program to evaluate the minimum Cost BomBom consumes before it destroys all enemy characters.

Input

  The input is given in the following format.

W H N
x_1 y_1
x_2 y_2
:
x_N y_N

The first line provides the number of squares in the horizontal direction W (1 ≤ W ≤ 105), in the vertical direction H (1 ≤ H ≤ 105), and the number of enemy characters N (1 ≤ N ≤ 105). Each of the subsequent N lines provides location information of the i-th enemy, column x_i (0 ≤ x_i ≤ W-1) and row y_i (0 ≤ y_i ≤ H-1). The number of enemy characters in a specific square can be either one or zero.

Output

  Output the minimum Cost in a line.

Sample Input 1

5 4 4
0 3
1 1
2 2
2 3

Sample Output 1

2

Sample Input 2

6 6 5
2 1
5 2
3 3
1 4
1 5

Sample Output 2

4

Sample Input 3

8 8 4
6 0
7 0
0 6
0 7

Sample Output 3

0



Sample input:
5 4 4
0 3
1 1
2 2
2 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
class Node(object):#Nodeを扱うクラス

    def __init__(self, name):
        self.name = name

    def getName(self):#Nodeの名前を返す
        return self.name

    def __str__(self):
        return self.name

class Node_W(Node):#重さ付きNodeを扱うクラス

    def __init__(self, name):
        self.name = name
        self.w = 0

    def addWeight(self,weight):
        self.w += weight




class Edge(object):#エッジを扱うクラス

    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def getSource(self):#親Nodeを返す
        return self.src

    def getDestination(self):#子Nodeを返す
        return self.dest

    def __str__(self):
        return self.src + "->" + self.dest

class Graph(object):

    def __init__(self):
        self.Nodes = []#グラフ上のNode
        self.Edges = {}#グラフ上のエッジ親Nodeのキーに対して子Nodeのリストを返す

    def addNode(self, node):#グラフにNodeを加える
        if(node in self.Nodes):
            raise ValueError("そのNodeはもうあるよ")
        else:
            self.Nodes.append(node)
            self.Edges[node] = []#nodeの子Nodeのリスト

    def addEdges(self, edge):#グラフ上にエッジを加える
        src = edge.getSource()
        dest = edge.getDestination()
        if src not in self.Nodes or dest not in self.Nodes:
            raise ValueError("そのNodeはグラフ上にありません")
        else:
            self.Edges[src].append(dest)

    def getChildList(self,node):#nodeの子Nodeのリストを返す
        return self.Edges[node]

    def put_player(self, x, y, W, H, L):#x, yはplayerの座標, W, Hはx, y座標の限界,Lは受け取ったNode_W型を含むリスト
        index = (H*y) + x
        if index >= H*W:
            raise ValueError("そんな座標はないよ")
        else:
            L[index].w = 1

    def __str__(self):
        s = ""
        for src in self.Nodes:
            for dest in self.Edges[src]:
                s = s + src.getNode() + "->" + dest.getNode() + '\n'
        return s


def ShowPath(path):#pathはNode_W型からなるリスト
    s = ""
    for nextNode in range(len(path)):
        s = s + path[nextNode].getName() + "(" +  str(path[nextNode].w) + ")"
        if nextNode != len(path) - 1:
            s = s + "->"
    return s

all_path1 = []#すべての経路を保存する
count = 0

def all_search(g, start, end, path, all_path, toPrint = True):#グラフ上の全経路を保存する
    path = path + [start]
    if toPrint == True:
        ShowPath(path)
        all_path.append(path)
    for child in g.getChildList(start):
        if child not in path:#ループはしない
            newpath = all_search(g,child,end,path,all_path,toPrint = True)


def make_field(W,H):
    #W,Hはint型
    point = [[0 for i in range(H)] for j in range(W)]
    for x in range(W):
        for y in range(H):
            point[x][y] = 0
    Nodes= [] #pointの要素数分だけNode_Wを作りリストに保存する
    for i in range(0,W * H,1):
        Nodes.append(Node_W(str(i)))
    g = Graph()
    for i in range(0,W*H, 1):#グラフ上にNodesで作ったNodeを追加する
        g.addNode(Nodes[i])
    for i in range(H):
        for w in range(W):
           num = (H*i) + w
           if(i != H - 1):#この時は下につなげるNodeがある
               g.addEdges(Edge(Nodes[num],Nodes[num + W]))
           if(w != W - 1):#この時は横につなげるNodeがある
               g.addEdges(Edge(Nodes[num], Nodes[num + 1]))
    return g

class Player(object):

    def __init__(self, x, y, L,g,W,H):#x,yはplayerを配置する座標, LはNode_W型を含むリスト,gはplayerを配置するField,W,Xはx座標y座標の限界
        g.put_player(x,y,W,H,L)
        

class Main(Player):

    def __init__(self,L,g,W,H):
        g.put_player(0,0,W,H,L)
        self.cost = 0
        self.now_position = 0
        self.W = W
        self.H = H
        self.L = L

    def move(self,g, node):#gはgraph型,nodeはNode型,与えられたNodeへ進む
        g.Nodes[self.now_position].w = 0
        self.now_position = int(node.getName())
        g.Nodes[self.now_position].w = 1
        if(int(node.getName()) == 0):
            self.cost += 0 #0番に移動する場合はコスト0
        else:
            self.cost += 1


    def destroy(self, g):
        h1 = self.H
        h2 = self.H
        mod = self.now_position % self.W
        i = 1
        j = 1
        g.Nodes[self.now_position].w = 0
        while(self.now_position - h1 >= 0):#現在位置の上の敵を消す
            g.Nodes[self.now_position - h1].w = 0
            h1 += self.H
        while(self.now_position + h2 < self.H * self.W):#現在位置の下の敵を消す
            g.Nodes[self.now_position + h2].w = 0
            h2 += self.H
        while((self.now_position - i)  % self.W != self.W - 1 and self.now_position - i < self.H * self.W):#現在位置の左の敵を消す
            g.Nodes[self.now_position - i].w = 0
            i += 1
        while((self.now_position + j) % self.W != 0 and self.now_position + j < self.H * self.W):#現在位置の右の敵を消す
            g.Nodes[self.now_position + j].w = 0
            j += 1

def ShowGraph(g,H,W):#gはgraph型
    result = ""
    for h in range(H):
        for w in range(W):
            result = result + g.Nodes[(H * h) + w].getName() + "(" + str(g.Nodes[(H*h) + w].w) + ")"
            if(w != W - 1):
                result = result + "->"
            else:
                result = result + '\n'
        if (h != H -1):
            for w in range(W):
                k = int(g.Nodes[(H*h) + w].getName())
                s = 0
                while(k//10 != 0):
                    s += 1
                    k /= 10
                result = result + "↓" + "    " + " "*s
                s = 0
                if(w == W - 1):
                    result = result + '\n'
    return result

def SearchWeight(g):#gはgraph型,graph上のNodeがすべて0ならTrue,それ以外ならFalseを返す
    for i in range(len(g.Nodes)):
        if g.Nodes[i].w == 1:
            return False
    return True


def test7():
     W, H, N = map(int, input().split())
     X = []
     Y = []
     min = H*W #最小のコストを保存
     g = make_field(W, H)
     all_path = []
     start = g.Nodes[0]
     end = g.Nodes[W*H - 1]
     for i in range(N):
         x, y = map(int, input().split())
         X.append(x)
         Y.append(y)
     all_search(g,start, end, [], all_path, toPrint = False)
     for root in all_path:
        for i in range(N):
         Player(X[i], Y[i], g.Nodes, g, W, H)
        main = Main(g.Nodes,g,W,H)
        for path in (root):
            main.move(g,path)
            main.destroy(g)
            if(SearchWeight(g) == True):
                if main.cost < min:
                    min = main.cost
                    break
     print(str(min))

test7()

Submission status: Wrong Answer

Solution code:
class Node(object):#Nodeを扱うクラス

    def __init__(self, name):
        self.name = name

    def getName(self):#Nodeの名前を返す
        return self.name

    def __str__(self):
        return self.name

class Node_W(Node):#重さ付きNodeを扱うクラス

    def __init__(self, name):
        self.name = name
        self.w = 0

    def addWeight(self,weight):
        self.w += weight




class Edge(object):#エッジを扱うクラス

    def __init__(self, src, dest):
        self.src = src
        self.dest = dest

    def getSource(self):#親Nodeを返す
        return self.src

    def getDestination(self):#子Nodeを返す
        return self.dest

    def __str__(self):
        return self.src + "->" + self.dest

class Graph(object):

    def __init__(self):
        self.Nodes = []#グラフ上のNode
        self.Edges = {}#グラフ上のエッジ親Nodeのキーに対して子Nodeのリストを返す

    def addNode(self, node):#グラフにNodeを加える
        if(node in self.Nodes):
            raise ValueError("そのNodeはもうあるよ")
        else:
            self.Nodes.append(node)
            self.Edges[node] = []#nodeの子Nodeのリスト

    def addEdges(self, edge):#グラフ上にエッジを加える
        src = edge.getSource()
        dest = edge.getDestination()
        if src not in self.Nodes or dest not in self.Nodes:
            raise ValueError("そのNodeはグラフ上にありません")
        else:
            self.Edges[src].append(dest)

    def getChildList(self,node):#nodeの子Nodeのリストを返す
        return self.Edges[node]

    def put_player(self, x, y, W, H, L):#x, yはplayerの座標, W, Hはx, y座標の限界,Lは受け取ったNode_W型を含むリスト
        k = W - H
        index = (H*y) + x + k*y
        if index >= H*W:
            raise ValueError("そんな座標はないよ")
        else:
            L[index].w = 1

    def __str__(self):
        s = ""
        for src in self.Nodes:
            for dest in self.Edges[src]:
                s = s + src.getNode() + "->" + dest.getNode() + '\n'
        return s


def ShowPath(path):#pathはNode_W型からなるリスト
    s = ""
    for nextNode in range(len(path)):
        s = s + path[nextNode].getName() + "(" +  str(path[nextNode].w) + ")"
        if nextNode != len(path) - 1:
            s = s + "->"
    return s

all_path1 = []#すべての経路を保存する
count = 0

def all_search(g, start, end, path, all_path, toPrint = True):#グラフ上の全経路を保存する
    path = path + [start]
    if toPrint == True:
        ShowPath(path)
        all_path.append(path)
    for child in g.getChildList(start):
        if child not in path:#ループはしない
            newpath = all_search(g,child,end,path,all_path,toPrint = True)


def make_field(W,H):
    #W,Hはint型
    k = 0
    if (W < H):
        k = W - H
    elif(W > H):
        k = W - H
    Nodes= [] #pointの要素数分だけNode_Wを作りリストに保存する
    for i in range(0,W * H,1):
        Nodes.append(Node_W(str(i)))
    g = Graph()
    for i in range(0,W*H, 1):#グラフ上にNodesで作ったNodeを追加する
        g.addNode(Nodes[i])
    for i in range(H):
        for w in range(W):
            num = (H*i) + w + k * i
            if(i != H - 1):#この時は下につなげるNodeがある
                g.addEdges(Edge(Nodes[num],Nodes[num + W]))
            if(w != W - 1):#この時は横につなげるNodeがある
                g.addEdges(Edge(Nodes[num], Nodes[num + 1]))
     
    return g

class Player(object):

    def __init__(self, x, y, L,g,W,H):#x,yはplayerを配置する座標, LはNode_W型を含むリスト,gはplayerを配置するField,W,Xはx座標y座標の限界
        g.put_player(x,y,W,H,L)
        

class Main(Player):

    def __init__(self,L,g,W,H):
        g.put_player(0,0,W,H,L)
        self.cost = 0
        self.now_position = 0
        self.W = W
        self.H = H
        self.L = L

    def move(self,g, node):#gはgraph型,nodeはNode型,与えられたNodeへ進む
        g.Nodes[self.now_position].w = 0
        self.now_position = int(node.getName())
        g.Nodes[self.now_position].w = 0
        if(int(node.getName()) == 0):
            self.cost += 0 #0番に移動する場合はコスト0
        else:
            self.cost += 1


    def destroy(self, g):
        h1 = self.H
        h2 = self.H
        mod = self.now_position % self.W
        i = 1
        j = 1
        k = self.W - self.H
        g.Nodes[self.now_position].w = 0
        while(self.now_position - h1 >= 0):#現在位置の上の敵を消す
            g.Nodes[self.now_position - h1].w = 0
            h1 += self.H - k
        while(self.now_position + h2 < self.H * self.W):#現在位置の下の敵を消す
            g.Nodes[self.now_position + h2].w = 0
            h2 += self.H + k
        while((self.now_position - i)  % self.W != self.W - 1 and self.now_position - i < self.H * self.W and self.now_position - i > 0):#現在位置の左の敵を消す
            g.Nodes[self.now_position - i].w = 0
            i += 1
        while((self.now_position + j) % self.W != 0 and self.now_position + j < self.H * self.W and self.now_position + j > 0):#現在位置の右の敵を消す
            g.Nodes[self.now_position + j].w = 0
            j += 1

def ShowGraph(g,H,W):#gはgraph型
    result = ""
    k = W - H
    for h in range(H):
        for w in range(W):
            result = result + g.Nodes[(H * h) + w +  k*h].getName() + "(" + str(g.Nodes[(H*h) + w + k * h].w) + ")"
            if(w != W - 1):
                result = result + "->"
            else:
                result = result + '\n'
        if (h != H -1):
            for w in range(W):
                t = int(g.Nodes[(H*h) + w + k * h].getName())
                s = 0
                while(t//10 != 0):
                    s += 1
                    t /= 10
                result = result + "↓" + "    " + " "*s
                s = 0
                if(w == W - 1):
                    result = result + '\n'
    return result

def SearchWeight(g):#gはgraph型,graph上のNodeがすべて0ならTrue,それ以外ならFalseを返す
    for i in range(len(g.Nodes)):
        if g.Nodes[i].w == 1:
            return False
    return True





def test1():#グラフが正常につくられているかテスト
    g = make_field(6,6)
    start = g.Nodes[0]
    end = g.Nodes[6*6 - 1]
    all_path = []
    all_search(g, start, end, [], all_path,toPrint = True )
    main = Player(0,0,g.Nodes,g,6,6)
    enemy1 = Player(1,1,g.Nodes,g, 6,6)
    enemy2 = Player(5,5,g.Nodes,g, 6,6)
    for i in range(len(all_path)):
        print(ShowPath(all_path[i]))
        print(str(i))


def test2():#正常に爆破ができるのかを確かめるテスト
    W, H = map(int, input().split())
    g = make_field(W, H)
    all_path = []
    start = g.Nodes[0]
    end = g.Nodes[W*H - 1]
    main = Main(g.Nodes,g,W,H)
    N = int(input())
    for i in range(N):
        x, y = map(int, input().split())
        Player(x, y, g.Nodes,g,W,H)
    all_search(g,start, end, [], all_path, toPrint = True)
    print(ShowGraph(g, H, W))
    main.move(g,g.Nodes[6])
    main.destroy(g)
    print("爆破！")
    print(ShowGraph(g,H,W))


def test3():#グラフ上のある経路を正常に動くのかテスト
     W, H = map(int, input().split())
     g = make_field(W, H)
     all_path = []
     start = g.Nodes[0]
     end = g.Nodes[W*H - 1]
     main = Main(g.Nodes,g,W,H)
     N = int(input())
     for i in range(N):
         x, y = map(int, input().split())
         Player(x, y, g.Nodes,g,W,H)
     all_search(g,start, end, [], all_path, toPrint = True)
     print(ShowPath(all_path[4]))
     print()#改行
     print(ShowGraph(g, H, W))
     print()#改行
     for path in (all_path[4]):
         main.move(g,path)
         print(str(path.getName())+"番に移動しました!")
         print()#改行
         print(ShowGraph(g, H, W))
         print()
         print("現在までのコスト :",str(main.cost))
         print()#改行
     for i in range(len(all_path)):
        print(ShowPath(all_path[i]))
        print(str(i))

def test4():#1つの経路で動くたびに爆発できるのかテスト
     W, H = map(int, input().split())
     g = make_field(W, H)
     all_path = []
     start = g.Nodes[0]
     end = g.Nodes[W*H - 1]
     main = Main(g.Nodes,g,W,H)
     N = int(input())
     for i in range(N):
         x, y = map(int, input().split())
         Player(x, y, g.Nodes,g,W,H)
     all_search(g,start, end, [], all_path, toPrint = True)
     print(ShowPath(all_path[4]))
     print()#改行
     print(ShowGraph(g, H, W))
     print()#改行
     for path in (all_path[4]):
         main.move(g,path)
         print(str(path.getName())+"番に移動しました!")
         print()#改行
         print(ShowGraph(g, H, W))
         main.destroy(g)
         print("爆破しました!")
         print(ShowGraph(g, H, W))
         print()
         print("現在までのコスト :",str(main.cost))
         print()#改行


def test5():#全経路に関して爆発を試す
     W, H = map(int, input().split())
     X = []
     Y = []
     g = make_field(W, H)
     all_path = []
     start = g.Nodes[0]
     end = g.Nodes[W*H - 1]
     N = int(input())
     for i in range(N):
         x, y = map(int, input().split())
         X.append(x)
         Y.append(y)
     all_search(g,start, end, [], all_path, toPrint = True)
     print()#改行
     print(ShowGraph(g, H, W))
     print()#改行
     for root in all_path:
        for i in range(N):
         Player(X[i], Y[i], g.Nodes, g, W, H)
        main = Main(g.Nodes,g,W,H)
        for path in (root):
            print(ShowPath(root))
            main.move(g,path)
            print(str(path.getName())+"番に移動しました!")
            print()#改行
            print(ShowGraph(g, H, W))
            main.destroy(g)
            print("爆破しました!")
            print(ShowGraph(g, H, W))
            if(SearchWeight(g) == True):
                print("全滅や!")
            else:
                print("まだ敵がおるで!")
            print()
            print("現在までのコスト :",str(main.cost))
            print()#改行

def test6():#全経路に関して爆発を試す
     W, H = map(int, input().split())
     X = []
     Y = []
     min = H*W #最小のコストを保存
     g = make_field(W, H)
     all_path = []
     start = g.Nodes[0]
     end = g.Nodes[W*H - 1]
     N = int(input())
     for i in range(N):
         x, y = map(int, input().split())
         X.append(x)
         Y.append(y)
     all_search(g,start, end, [], all_path, toPrint = True)
     print()#改行
     print(ShowGraph(g, H, W))
     print()#改行
     for root in all_path:
        for i in range(N):
         Player(X[i], Y[i], g.Nodes, g, W, H)
        main = Main(g.Nodes,g,W,H)
        for path in (root):
            print(ShowPath(root))
            main.move(g,path)
            print(str(path.getName())+"番に移動しました!")
            print()#改行
            print(ShowGraph(g, H, W))
            main.destroy(g)
            print("爆破しました!")
            print(ShowGraph(g, H, W))
            if(SearchWeight(g) == True):
                print("全滅や!")
                if main.cost < min:
                    min = main.cost
                    break
            else:
                print("まだ敵がおるで!")
            print()
            print("現在までのコスト :",str(main.cost))
            print()#改行
        print("現在の最小コスト :",str(min))

def test7():
     W, H, N = map(int, input().split())
     X = []
     Y = []
     l = 0
     min = H*W #最小のコストを保存
     g = make_field(W, H)
     all_path = []
     start = g.Nodes[0]
     end = g.Nodes[W*H - 1]
     for i in range(N):
         x, y = map(int, input().split())
         X.append(x)
         Y.append(y)
     all_search(g,start, end, [], all_path, toPrint = False)
     for root in all_path:
        for i in range(N):
         Player(X[i], Y[i], g.Nodes, g, W, H)
        main = Main(g.Nodes,g,W,H)
        for path in (root):
            main.move(g,path)
            main.destroy(g)
            if(SearchWeight(g) == True):
                if main.cost < min:
                    min = main.cost
                    l = root
                    break
     print(str(min))
     print(ShowPath(l))
     for i in range(N):
         Player(X[i], Y[i], g.Nodes, g, W, H)
     main = Main(g.Nodes, g, W, H)
     for path in (root):
            print(ShowPath(root))
            main.move(g,path)
            print(str(path.getName())+"番に移動しました!")
            print()#改行
            print(ShowGraph(g, H, W))
            main.destroy(g)
            print("爆破しました!")
            print(ShowGraph(g, H, W))
            if(SearchWeight(g) == True):
                print("全滅や!")
                break
            else:
                print("まだ敵がおるで!")
            print()
            print("現在までのコスト :",str(main.cost))
            print()#改行
         
def test8():
     W, H, N = map(int, input().split())
     X = []
     Y = []
     min = H*W #最小のコストを保存
     g = make_field(W, H)
     all_path = []
     start = g.Nodes[0]
     end = g.Nodes[W*H - 1]
     for i in range(N):
         x, y = map(int, input().split())
         X.append(x)
         Y.append(y)
     all_search(g,start, end, [], all_path, toPrint = False)
     for root in all_path:
        for i in range(N):
         Player(X[i], Y[i], g.Nodes, g, W, H)
        main = Main(g.Nodes,g,W,H)
        for path in (root):
            main.move(g,path)
            main.destroy(g)
            if(SearchWeight(g) == True):
                if main.cost < min:
                    min = main.cost
                    break
     print(str(min))

test8()