2次元配列アクセスの高速化

###前提・実現したいこと
pythonを使用して、アルゴリズムの勉強をしています。
Aizu Online Judgeの 0092 Square Searching という問題を2次元配列(リストのリスト)を使用して解くには解いたのですが、制限時間ギリギリなので高速化できないかと考えています。
pythonで2次元配列を使用する場合、どのように書くと速くなるでしょうか。

###発生している問題・エラーメッセージ
プロファイラで確認したところ、ソース中の for y, for xループ中のdp[][]へのアクセス部分で実効時間の大部分を消費しているようです。

###該当のソースコード

python
1import sys
2
3# オンラインジャッジシステムでの処理時間: 約3.5秒
4def find_square0(data):
5    max_size = 0
6    dp = [] # dp用の2次元配列
7    # '.'のマスを1に、'*'のマスを0に初期化
8    for row in data:
9        temp = []
10        for c in row:
11            if c == '.':
12                temp.append(1)
13                max_size = 1
14            else:
15                temp.append(0)
16        dp.append(temp)
17
18    # 対象のマスから左上に向かって、何マスの正方形が確保できるかチェックする
19    for y in range(1, len(dp)):
20        for x in range(1, len(dp[0])):
21            if dp[y][x] == 1:
22                dp[y][x] = min(dp[y-1][x-1], dp[y-1][x], dp[y][x-1]) + 1
23                if dp[y][x] > max_size:
24                    max_size = dp[y][x]
25    return max_size
26
27def main(args):
28    while True:
29        n = int(input())
30        if n == 0:
31            break
32        data = [input() for _ in range(n)]
33        result = find_square0(data)
34        print(result)
35
36
37if __name__ == '__main__':
38    main(sys.argv[1:])

###試したこと
リストのリストにアクセスしているから遅いのだろうと考え、以下のように変更してみましたが、少し(2割くらい)改善しただけでした。

python
1# オンラインジャッジシステムでの処理時間: 約2.8秒
2def find_square2(data):
3    max_size = 0
4    dp = [[0]*len(data[0]) for _ in range(len(data))] # dp用の2次元配列
5    # '.'のマスを1に、'*'のマスを0に初期化
6    for y, row in enumerate(data):
7        for x, c in enumerate(row):
8            if c == '.':
9                dp[y][x] = 1
10                max_size = 1
11
12    # 現在行(curr_row)と一つ上の行(prev_row)のみ必要なので、名前を付けてアクセスできるようにした
13    prev_row = dp[0]
14    for curr_row in dp[1:]:
15        for x, t in enumerate(curr_row[1:], start=1):
16            if t == 1:
17                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
18                if curr_row[x] > max_size:
19                    max_size = curr_row[x]
20        prev_row = curr_row
21    return max_size

また、dpの宣言を以下のようにarrayのリストに変更してみましたが、速度は改善しませんでした。

python
1dp = [array('I', [0]*len(data[0])) for _ in range(len(data))]

2017-08-28追記
okateimさんにコメントいただいた、配列(リスト)の1次元化を試してみました。
配列を一つだけ確保する方式だと、配列のサイズが大きくなった時の速度ペナルティが厳しいようです。

python
1# サイズ固定、オンラインジャッジシステムでの処理時間: 約4.9秒
2def find_square4(data):
3    max_size = 0
4    dp = [0 for _ in range(1024*1024)]
5    # '.'のマスを1に
6    for y, row in enumerate(data):
7        for x, c in enumerate(row):
8            if c == '.':
9                dp[y*1024+x] = 1
10
11    # 対象のマスから左上に向かって、何マスの正方形が確保できるかチェックする
12    for y in range(1, len(data)):
13        for x in range(1, len(data)):
14            if dp[y*1024+x] == 1:
15                dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
16                if dp[y*1024+x] > max_size:
17                    max_size = dp[y*1024+x]
18    return max_size

python
1# サイズ可変、オンラインジャッジシステムでの処理時間: 約5.2秒
2def find_square4_2(data):
3    max_size = 0
4    n = len(data)
5    dp = [0 for _ in range(n**2)]
6    # '.'のマスを1に
7    for y, row in enumerate(data):
8        for x, c in enumerate(row):
9            if c == '.':
10                dp[y*n+x] = 1
11
12    # 対象のマスから左上に向かって、何マスの正方形が確保できるかチェックする
13    for y in range(1, len(data)):
14        for x in range(1, len(data)):
15            if dp[y*n+x] == 1:
16                dp[y*n+x] = min(dp[(y-1)*n+x-1], dp[(y-1)*n+x], dp[y*n+x-1]) + 1
17                if dp[y*n+x] > max_size:
18                    max_size = dp[y*n+x]
19    return max_size