首页 > 搜索 > BFS搜索 > POJ 3318 Matrix Multiplication [解题报告] Java
2013
11-12

POJ 3318 Matrix Multiplication [解题报告] Java

Matrix Multiplication

问题描述 :

You are given three n × n matrices A, B and C. Does the equation A × B = C hold true?

输入:

The first line of input contains a positive integer n (n ≤ 500) followed by the the three matrices A, B and C respectively. Each matrix’s description is a block of n × n integers.

It guarantees that the elements of A and B are less than 100 in absolute value and elements of C are less than 10,000,000 in absolute value.

输出:

Output "YES" if the equation holds true, otherwise "NO".

样例输入:

2
1 0
2 3
5 1
0 8
5 1
10 26

样例输出:

YES

温馨提示:

Multiple inputs will be tested. So O(n3) algorithm will get TLE.

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
	InputStreamReader is=new InputStreamReader(System.in);
	BufferedReader in=new BufferedReader(is);
	int a=Integer.parseInt(in.readLine());
	int[][] p1=new int[a][a];
	int[][] p2=new int[a][a];
	int[][] p3=new int[a][a];
	for(int i=0;i< a;i++)
	{
		String[] ss=in.readLine().split(" ");
		for(int j=0;j< a;j++)
		  p1[i][j]=Integer.parseInt(ss[j]);
	}
	for(int i=0;i< a;i++)
	{
		String[] ss=in.readLine().split(" ");
		for(int j=0;j< a;j++)
		  p2[i][j]=Integer.parseInt(ss[j]);
	}
	for(int i=0;i< a;i++)
	{
		String[] ss=in.readLine().split(" ");
		for(int j=0;j< a;j++)
		  p3[i][j]=Integer.parseInt(ss[j]);
	}
      int i;
      if(a< 50) i=Math.min(2000, a*a);
      else if(a< 100) i=5000;
      else i=50000;
      while((i--)>0)
     {
	 int x=(int)(Math.random()*a);
	 int y=(int)(Math.random()*a);
	 int ans=0;
	 for(int j=0;j< a;j++)
		 ans+=p1[x][j]*p2[j][y];
	 if(ans!=p3[x][y]) break;
     }
     if(i==-1) System.out.println("YES");
     else System.out.println("NO");
  }
}

  1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  4. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])